迭代算法与递归算法的概念及区别

核心提示：【问题】 背包问题问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，迭代算法与递归算法的概念及区别(3)，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大，算法不会在该分支继续查找，而是立即终止该分支，设n 件物品的重量分别为w0、w1、…、wn-1，物品

　　【问题】 背包问题

问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

设n 件物品的重量分别为w0、w1、…、wn-1，物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option[ ]，该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。

对于第i件物品的选择考虑有两种可能：

(1) 考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。
　　(2) 考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。

按以上思想写出递归算法如下：

以下是引用片段：
　　try(物品i，当前选择已达到的重量和，本方案可能达到的总价值tv)
　　{/*考虑物品i包含在当前方案中的可能性*/
　　if(包含物品i是可以接受的)
　　{将物品i包含在当前方案中;
　　if(i
　　try(i+1,tw+物品i的重量,tv);
　　else
　　/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/
　　以当前方案作为临时最佳方案保存;
　　恢复物品i不包含状态;
　　}
　　/*考虑物品i不包含在当前方案中的可能性*/
　　if(不包含物品i仅是可男考虑的)
　　if(i
　　try(i+1,tw,tv-物品i的价值);
　　else
　　/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/
　　以当前方案作为临时最佳方案保存;
　　}
　　为了理解上述算法，特举以下实例。设有4件物品，它们的重量和价值见表：

物品 0 1 2 3

重量 5 3 2 1

价值 4 4 3 1

并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。

按上述算法编写函数和程序如下：

【程序】

以下是引用片段：
　　#include
　　#defineN100
　　doublelimitW,totV,maxV;
　　intoption[N],cop[N];
　　struct{doubleweight;
　　doublevalue;
　　}a[N];
　　intn;
　　voidfind(inti,doubletw,doubletv)
　　{intk;
　　/*考虑物品i包含在当前方案中的可能性*/
　　if(tw+a.weight<=limitW)
　　{cop=1;
　　if(i
　　else
　　{for(k=0;k
　　option[k]=cop[k];
　　maxv=tv;
　　}
　　cop=0;
　　}
　　/*考虑物品i不包含在当前方案中的可能性*/
　　if(tv-a.value>maxV)
　　if(i
　　else
　　{for(k=0;k
　　option[k]=cop[k];
　　maxv=tv-a.value;
　　}
　　}
　　voidmain()
　　{intk;
　　doublew,v;
　　printf(“输入物品种数
”);
　　scanf((“%d”,&n);
　　printf(“输入各物品的重量和价值
”);
　　for(totv=0.0,k=0;k
　　{scanf(“%1f%1f”,&w,&v);
　　a[k].weight=w;
　　a[k].value=v;
　　totV+=V;
　　}
　　printf(“输入限制重量
”);
　　scanf(“%1f”,&limitV);
　　maxv=0.0;
　　for(k=0;kfind(0,0.0,totV);
　　for(k=0;k
　　if(option[k])printf(“%4d”,k+1);
　　printf(“
总价值为%.2f
”,maxv);
　　}