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

精选优质文档-倾情为你奉上#include<stdio.h>int 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(i>n) Print();if(bestPrice>bp)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; Backtracking(i+1); void Print() int i;printf("n路径为 "); for(i=1;i<n;+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;i<n;+i) printf("%d,",bAi);printf("%dt总价值为 %dn",bAi,bp); printf("nn总共搜索结点数%dn",times);专心-专注-专业