#define N 5
#include
#include
int d[N][N];
int Way[N];
void Sort(int a[],int low,int up)//排序
{
int i,j,k,t;
for(i=low+1;i
for(j=low;j
if(a[j]>a[i])
{
t=a[i];
for(k=i;k>j;k--) a[k]=a[k-1];
a[j]=t;
break;
}
}
int Work(int a[],int n,int b)//解决问题
{
int i,j,k,t,cost,min;
cost=0;min=0;
long s,count;
Sort(a,0,n-1);
min+=d[b][a[0]];
for(i=0;i
min+=d[a[i]][b];
for(i=0;i
s=1;
for(i=1;i
for(count=2;count
{
j=n-1;
while(a[j-1]>a[j]) j--;
k=j; a[k]=a[j];
for(i=j+1;i
if(a[k]>a[i]&&a[i]>a[j-1])
{k=i;a[k]=a[i];}
t=a[k];a[k]=a[j-1];a[j-1]=t;
Sort(a,j,n-1);
cost+=d[b][a[0]];
for(i=0;i
cost+=d[a[i]][b];
if(cost
{
min=cost;
for(i=0;i
}
cost=0;
}
return min;
}
void main()//主函数
{
int a,n=N,s,i,j,v[N],k;
while(1)
{
printf(" =================货郎担问题的穷举解法=================\n\n\n");
printf(" 1 ---------------输入数据---------------\n");
printf(" 2 ---------------输出原始数据---------------\n");
printf(" 3 ---------------解决问题---------------\n");
printf(" 4 ---------------输出最终结果---------------\n");
printf(" 0 ---------------退出系统---------------\n\n");
printf("请选择相应序号：");
scanf("%d",&k);
printf("\n");
switch(k)
{
case 1:
{
for(i=0;i
v[i]=i;
printf("请输入出发村庄的编号（从1——%d）",n);
scanf("%d",&a);
a=a-1;
getchar();
for(i=a;i
v[i]=v[i+1];
printf("\n请输入各个城市之间的距离数据：(共有 %d 个城市，%d 个数据)\n",n,n*n);
for(i=0;i
for(j=0;j
{
scanf("%d",&d[i][j]);
}
printf("输入完毕！\n");
system("pause");
system("cls");break;
}
case 2:
{
printf("输入各个村庄的距离如下:\n");
for(i=0;i
{
for(j=0;j
printf("%3d",d[i][j]);
printf("\n");
}
system("pause");
system("cls");break;
}
case 3:
{
s=Work(v,n-1,a);
printf("问题解决完毕！\n");
system("pause");
system("cls");
break;
}
case 4:
{
printf("最短路径为\n%d ",a+1);
for(i=0;i
printf("%d\n",a+1);
printf("最小值为 %d\n",s);
system("pause");
system("cls");break;
}
case 0:
{
printf("\n谢谢使用！\n");
exit(0);break;
}
default:{
printf("对不起，您的输入有误。。。。\n");
system("pause");
system("cls");
}
}
}
}
#define N 5
#include
#include
int d[N][N];
int Way[N];
void Sort(int a[],int low,int up)//排序
{
int i,j,k,t;
for(i=low+1;i
for(j=low;j
if(a[j]>a[i])
{
t=a[i];
for(k=i;k>j;k--) a[k]=a[k-1];
a[j]=t;
break;
}
}
int Work(int a[],int n,int b)//解决问题
{
int i,j,k,t,cost,min;
cost=0;min=0;
long s,count;
Sort(a,0,n-1);
min+=d[b][a[0]];
for(i=0;i
min+=d[a[i]][b];
for(i=0;i
s=1;
for(i=1;i
for(count=2;count
{
j=n-1;
while(a[j-1]>a[j]) j--;
k=j; a[k]=a[j];
for(i=j+1;i
if(a[k]>a[i]&&a[i]>a[j-1])
{k=i;a[k]=a[i];}
t=a[k];a[k]=a[j-1];a[j-1]=t;
Sort(a,j,n-1);
cost+=d[b][a[0]];
for(i=0;i
cost+=d[a[i]][b];
if(cost
{
min=cost;
for(i=0;i
}
cost=0;
}
return min;
}
void main()//主函数
{
int a,n=N,s,i,j,v[N],k;
while(1)
{
printf(" =================货郎担问题的穷举解法=================\n\n\n");
printf(" 1 ---------------输入数据---------------\n");
printf(" 2 ---------------输出原始数据---------------\n");
printf(" 3 ---------------解决问题---------------\n");
printf(" 4 ---------------输出最终结果---------------\n");
printf(" 0 ---------------退出系统---------------\n\n");
printf("请选择相应序号：");
scanf("%d",&k);
printf("\n");
switch(k)
{
case 1:
{
for(i=0;i
v[i]=i;
printf("请输入出发村庄的编号（从1——%d）",n);
scanf("%d",&a);
a=a-1;
getchar();
for(i=a;i
v[i]=v[i+1];
printf("\n请输入各个城市之间的距离数据：(共有 %d 个城市，%d 个数据)\n",n,n*n);
for(i=0;i
for(j=0;j
{
scanf("%d",&d[i][j]);
}
printf("输入完毕！\n");
system("pause");
system("cls");break;
}
case 2:
{
printf("输入各个村庄的距离如下:\n");
for(i=0;i
{
for(j=0;j
printf("%3d",d[i][j]);
printf("\n");
}
system("pause");
system("cls");break;
}
case 3:
{
s=Work(v,n-1,a);
printf("问题解决完毕！\n");
system("pause");
system("cls");
break;
}
case 4:
{
printf("最短路径为\n%d ",a+1);
for(i=0;i
printf("%d\n",a+1);
printf("最小值为 %d\n",s);
system("pause");
system("cls");break;
}
case 0:
{
printf("\n谢谢使用！\n");
exit(0);break;
}
default:{
printf("对不起，您的输入有误。。。。\n");
system("pause");
system("cls");
}
}
}
}