01背包问题回溯法解决子集树

//回溯法 #include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; int c; //背包容量 int n; //物品数 int weight[100]; //存放n个物品重量的数组 int price[100]; //存放n个物品价值的数组 int currentWeight = 0; //当前重量 int bestPrice = 0; //当前最优值 int bestAnswer[100]; //当前最优解 int bp = 0; //最优值 int bA[100]; //当前最优解 int times = 0; //浏览节点数 int m=0; void Print() { int i; printf("\n路径为 {"); for(i = 1; i < n; ++i) printf("%d,", bestAnswer[i]); printf("%d}\t价值为%d\n", bestAnswer[i], bestPrice); } class Object { public: int ID; double d; }; int cmp(Object a,Object b)//定于排序类型。 { return a.d>b.d; //降序,按照价值比来排序，即每单位重量的价值 } double Bound(int i) { Object *Q=new Object[n+1]; int j; for(j = 1; j <= n; j++) { Q[j].ID = j; Q[j].d = 1.0 * price[j] / weight[j]; } sort(Q+1, Q+n+1, cmp);//对数组Q排序，按cmp()方式排序。这里要注意是从Q[1]开始到Q[n+1] double cleft = c-currentWeight; //剩余的重量空间 double b = bestPrice; //目前得到的价值 while(i <= n && weight[Q[i].ID] <= cleft) { cleft -= weight[Q[i].ID]; //得到更高的价值，在最好情况下 b += price[Q[i].ID]; i++; } if(i <= n) b += 1.0*price[Q[i].ID] * cleft / weight[Q[i].ID];/*如果不能完整装入一个物品，则可以装入部分。*/ return b; //返回此时能够得到的最好的价值 } void Backtracking(int i) { times += 1; if(i > n) //到达最后一层，进行输出 { Print(); //找到此次路线的解 if(bestPrice > bp) //是更优的 { bp = bestPrice; for(int j = 1; j <= n; j++) bA[j] = bestAnswer[j]; //找到更优解，转至bA中，便于输出 } return; } if(currentWeight + weight[i] <= c) { //将物品i放入背包，搜索左子树 bestAnswer[i] = 1; currentWeight += weight[i]; bestPrice += price[i]; Backtracking(i+1); //完成上面的递归，返回到上一结点，物品i不放入背包，准备递归右子树 //bestAnswer[i] = 0; currentWeight -= weight[i]; bestPrice -= price[i]; } if(Bound(i+1) > bp) //right,限界 { bestAnswer[i] = 0; //记录进入右子树 Backtracking(i+1); } //bestAnswer[i] = 0; //若Bound不懂，则将if注释掉，只使用if内两行 //Backtracking(i+1);//Bound是限界，剪枝使用 } int main() { int i; //输入部分 printf("请输入物品的数量:"); scanf("%d", &n); printf("请输入背包的容量(能承受的重量):"); scanf("%d", &c); printf("请依次输入%d个物品的重量:\n", n); for(i = 1; i <= n; i++) scanf("%d", &weight[i]); printf("请依次输入%d个物品的价值:\n",n); for(i = 1; i <= n; i++) scanf("%d", &price[i]); printf("各符合条件的路径为：\n"); Backtracking(1); printf("*******************************************************\n"); printf("\nthe best answer is {"); for(i=1; i<n; ++i) printf("%d,", bA[i]); printf("%d}\tthe best price is %d\n", bA[i], bp); printf("\n\n总共搜索结点数%d\n", times); return 0; } /* 请输入物品的数量:4 请输入背包的容量(能承受的重量):7 请依次输入4个物品的重量: 3 5 2 1 请依次输入4个物品的价值: 9 10 7 4 各符合条件的路径为： 路径为 {1,0,1,1} 价值为20 ******************************************************* the best answer is {1,0,1,1} the price is 20 总共搜索结点数5 Process returned 0 (0x0) execution time : 10.829 s Press any key to continue. */