软考常用算法设计方法(一)(3)

作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品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[i].flg=1;
　　 twv[i].tw=tw;
　　 twv[i].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[i].flg;
　　 tw=twv[i].tw;
　　 tv=twv[i].tv;
　　 switch(f)
　　 { case 1: twv[i].flg++;
　　 if (tw+a[i].weight<=limitw)
　　 if (i　　 { next(i+1,tw+a[i].weight,tv);
　　 i++;
　　 }
　　 else
　　 { maxv=tv;
　　 for (k=0;k　　 cop[k]=twv[k].flg!=0;
　　 }
　　 break;
　　 case 0: i--;
　　 break;
　　 default: twv[i].flg=0;
　　 if (tv-a[i].value>maxv)
　　 if (i　　 { next(i+1,tw,tv-a[i].value);
　　 i++;
　　 }
　　 else
　　 { maxv=tv-a[i].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(“%1f”,&limitw);
　　printf(“输入各物品的重量和价值\n”);
　　 for (k=0;k　　 scanf(“%1f%1f”,&a[k].weight,&a[k].value);
　　 maxv=find(a,n);
　　 printf(“\n选中的物品为\n”);
　　for (k=0;k　　 if (option[k]) printf(“%4d”,k+1);
　　 printf(“\n总价值为%.2f\n”,maxv);
　　}