用回溯法解决0-1背包问题(共4页).docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《用回溯法解决0-1背包问题(共4页).docx》由会员分享,可在线阅读,更多相关《用回溯法解决0-1背包问题(共4页).docx(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上#includeint c; /背包容量 int n; /物品数 int weight100; /存放n个物品重量的数组 int price100; /存放n个物品价值的数组 int currentWeight=0; /当前重量 int currentPrice=0; /当前价值 int bestPrice=0; /当前最优值 int bestAnswer100; /当前最优解 int bp=0;int bA100; /当前最优解 int times=0;void Print(); void Backtracking(int i) times+=1;if(in) Pr
2、int();if(bestPricebp)bp=bestPrice;for(int j=1;j=n;j+)bAj=bestAnswerj;return; if(currentWeight+weighti=c) /将物品i放入背包,搜索左子树 bestAnsweri = 1; currentWeight += weighti; bestPrice += pricei; Backtracking(i+1); /完成上面的递归,返回到上一结点,物品i不放入背包,准备递归右子树 currentWeight -= weighti; bestPrice -= pricei; bestAnsweri = 0
3、; Backtracking(i+1); void Print() int i;printf(n路径为 ); for(i=1;in;+i) printf(%d,bestAnsweri); printf(%dt价值为%dn,bestAnsweri,bestPrice); void main() int i;/*输入部分*/printf(请输入物品的数量:n); scanf(%d,&n); printf(请输入背包的容量(能承受的重量):n); scanf(%d,&c); printf(请依次输入%d个物品的重量:n,n);for(i=1;i=n;i+)scanf(%d,&weighti);printf(请依次输入%d个物品的价值:n,n);for(i=1;i=n;i+)scanf(%d,&pricei);printf(各符合条件的路径为:n); Backtracking(1);printf(*n);printf(n最优解路径为 ); for(i=1;in;+i) printf(%d,bAi);printf(%dt总价值为 %dn,bAi,bp); printf(nn总共搜索结点数%dn,times);专心-专注-专业
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 解决 背包 问题
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内