经典ACM算法合集经典ACM算法合集(12)

3> 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量
（即 cw-=w[i]*x[i],cp-=p[i]*x[i]）；
4> 当j>1时，for循环结束；
③ 当i=1时，若已测试完所有装载方案，外层调用就全部结束；
c. 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。

4、源程序：

#include<stdio.h>
int n,c,bestp;
int p[10000],w[10000],x[10000],bestx[10000];

void Backtrack(int i,int cp,int cw)
{
int j;
if(i>n)
{
if(cp>bestp)
{
bestp=cp;
for(i=0;i<=n;i++)
bestx[i]=x[i];
}
}
else
for(j=0;j<=1;j++)
{
x[i]=j;
if(cw+x[i]*w[i]<=c)
{
cw+=w[i]*x[i];
cp+=p[i]*x[i];
Backtrack(i+1,cp,cw);
cw-=w[i]*x[i];
cp-=p[i]*x[i];
}
}
}

main()
{
int i;
bestp=0;
scanf("%d%d",&n,&c);
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
Backtrack(1,0,0);
printf("Optimal value is\n");
printf("%d\n",bestp);
for(i=1;i<=n;i++)
printf("%d ",bestx[i]);
return 0;
}


5、算法分析：
递归函数Backtrack (i,cp,cw)遍历子集树的时间复杂度为，主
函数调用递归函
数Backtrack(1,0,0)，故该算法的时间复杂度为。
实验十三 最小重量机器设计问题

1、问题描述：
? 设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设 wij 是从供应商j 处购得的部件i的重量，cij

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(12)全文阅读和word下载服务。