用回溯法解决0-1背包问题

《用回溯法解决0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#includeintc;//背包容量intn;//物品数intweight[100];//存放n个物品重量的数组intprice[100];//存放n个物品价值的数组intcurrentWeight=0;//当前重量intcurrentPrice=0;//当前价值intbestPrice=0;//当前最优值intbestAnswer[100];//当前最优解intbp=0;intbA[100];//当前最优解inttimes=0;voidPrint();voidBacktracking(inti){times+=1;if

2、(i>n){Print();if(bestPrice>bp){bp=bestPrice;for(intj=1;j<=n;j++)bA[j]=bestAnswer[j];}return;}if(currentWeight+weight[i]<=c){//将物品i放入背包，搜索左子树bestAnswer[i]=1;currentWeight+=weight[i];bestPrice+=price[i];Backtracking(i+1);//完成上面的递归，返回到上一结点，物品i不放入背包，准备递归右子树currentWeight-=weigh

3、t[i];bestPrice-=price[i];}bestAnswer[i]=0;Backtracking(i+1);}voidPrint(){inti;printf("路径为{");for(i=1;i

4、");scanf("%d",&c);printf("请依次输入%d个物品的重量:",n);for(i=1;i<=n;i++)scanf("%d",&weight[i]);printf("请依次输入%d个物品的价值:",n);for(i=1;i<=n;i++)scanf("%d",&price[i]);printf("各符合条件的路径为：");Backtracking(1);printf("*******************************************************");printf("

5、n最优解路径为{");for(i=1;i