用回溯法解决0-1背包问题(共4页).docx

《用回溯法解决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);专心-专注-专业