背包问题的递归解法和非递归解法

《背包问题的递归解法和非递归解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、背包问题：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。[算法]try(物品i,当前选择已达到的重量之和tw,本方案可能达到的总价值tv){//考虑物品i包含在当前方案中的可能性 if(包含物品i是可接受的) {  将物品i包含在当前的方案中：  if(i

2、复物品i不包含状态； } //考虑物品i不包含在当前方案中的可能性 if(不包含物品i是可考虑的) {  if(i#include#

3、defineN100doublelimitW,   //限制得总重量  totV(0),  //全部物品的总价值  maxv;intoption[N],   //解的选择情况 cop[N];    //当前解的选择情况struct { doubleweight; doublevalue;}a[N];intn;     //物品总数voidfind(inti,doubletw,doubletv){ intk; //考虑物品i包含在当前方案中的可能性 if(tw+a[i].weight<=limitW)  //包含物品i是可接受的 {  cop[i

4、]=1;      //将物品i包含在方案中  if(imaxv) {  if(i

5、  for(k=0;k

6、"); scanf("%lf",&limitW); maxv=0.0;  for(k=0;k

7、递归#include#include#defineN100doublelimitW;intcop[N]; //临时最佳候选解的物品选择方案，当opts[i]为1，物品i在解中structele{ doubleweight; doublevalue;}a[N];intk,n;struct {intflg;  //物品的考虑状况：0:不选，1:将被考虑，2:曾被选中 doubletw; doubletv;}twv[N];  //当前候选解中各物品的考虑和选择状态，以及置该物品候选解的状态voidnext(int

8、i,doubletw,doubletv) //将考虑物品i{ twv[i].flg=1; twv[i].tw=tw; twv[i].tv=tv;}do