《用回溯法解决0-1背包问题.docx》由会员分享，可在线阅读，更多相关《用回溯法解决0-1背包问题.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) Print();if(best
2、Pricebp)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; Backtrackin
3、g(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);
