n”);
scanf(“ ”,&limitV);
maxv=0.0;
for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“M”,k+1); printf(“\\n总价值为%.2f\\n”,maxv); } 作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；反之，该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int flg; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.flg=1; twv.tw=tw; twv.tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.flg; tw=twv.tw; tv=twv.tv; switch(f) { case 1: twv.flg++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].flg!=0; } break; case 0: i--; break; default: twv.flg=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].flg!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\\n”); scanf((“%d”,&n); printf(“输入限制重量\\n”); scanf(“ ”,&limitW); printf(“输入各物品的重量和价值\\n”); for (k=0;k scanf(“ ”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\\n选中的物品为\\n”); for (k=0;k if (option[k]) printf(“M”,k+1); printf(“\\n总价值为%.2f\\n”,maxv); } 递推法 acm常用算法设计方法介绍 free发表于17小时 25分钟前 来源：www.608088.com 标签：算法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 【问题】 阶乘计算 问题描述：编写程序，对给定的n（n≦