货郎担问题或旅行商问题动态规划算法
#include
#include
#define maxsize 20
int n;
int cost[maxsize][maxsize];
int visit[maxsize]={1}; //表示城市0已经被加入访问的城市之中
int start = 0; //从城市0开始
int imin(int num, int cur)
{
int i;
if(num==1) //递归调用的出口
return cost[cur][start]; //所有节点的最后一个节点，最后返回 最后一个节点到起点的路径
int mincost = 10000;
for(i=0; i
{
//printf("%d-------%d\n",i,visit[i]);
if(visit[i]==0 && i!=start) //该结点没加入 且 非起始点
{
/*if(mincost
{
continue; //其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break
} */
visit[i] = 1; //递归调用时，防止重复调用
int value = cost[cur][i] + imin(num-1, i);
if(mincost > value)
{
mincost = value;
}
visit[i] = 0;//本次递归调用完毕，让下次递归调用
}
}
return mincost;
}
int main()
{
int i,j;
// int k,e,w;
n=4;
int cc[4][4]={{0,10,15,20},
{5,0,9,10},
{6,13,0,12},
{8,8,9,0}};
for(i=0; i
{
for(j=0; j
{
cost[i][j]=cc[i][j];
}
}
imin(n,start);
printf("把每个城市访问一次并返回原点最小费用%d\n",imin(n,start));
return 0;
}