递归解决背包问题

问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的方案，使得选中物品的总重量不超过指定的限制重量，但选中的物品总价值最大。揭解法描述：采用递归寻找物品的寻找方案。设前面已有多种选择方案，并保留其中总价值最大的方案与一个数组option[]中，该方案的总价值存于变量maxval中，当前正在考虑新方案，其物品选择情况存于数组cop[]中。假设当前方案已经考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品中良之和为tw；至此，若其余物品都选择是可能的话，本方案能到达的中间值得期望为tv。算法引入tv是当一旦当前方案的总价值的期望也小于前面方案的总价值maxval时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一方案。因为当前方案的总价值不比maxval大时，该方案不会再被考虑，这同时保证函数后找到的方案一定会比前面的方案好。对于第i件物品的选择考虑有两种情况：(1)：考虑物品 i 被选择，这种可能性仅当包含他不会超过总重量限制时才是可行的。选中后，继续递归去考查其余物品的选择。(2)：考虑物品 i 不被选择，这种可能性仅当不包含物品 i 也有可能找到价值更大的方案的情况。

代码：

#include<iostream> using namespace std; struct bag { int weight; //包的重量 int value; //包的价值 }arr[100]; int option[100]; //用于保存满足的最大值方案 int cop[100]; //用于标识每个包是否被选取 int maxv, limitw, totv; int n; void find(int i, int tw, tv) { int k; if(tw + arr[i].weight <= limitw) //该包被选取 { cop[i] = 1; //设立标记 if(i < n - 1) { find(i + 1, tw + arr[i].weight, tv); //递归判断下一个包 } else { for(k = 0; k < n; k++) { option[k] = cop[k]; //保存包被选取的信息 } maxv = tv; //获取最大价值 } cop[i] = 0; //还原cop数组 } if(tv - arr[i].value > maxv) //该包没有被选取，判断该方案的价值是否最大。如果不是，继续寻找下一个包 { if(i < n - 1) { find(i + 1, tw, tv - arr[i].value); } else { for(k = 0; k < n; k++) { option[k] = cop[k]; //保存包被选取的信息 } maxv = tv - arr[i].value; //获取最大价值 } } } int main() { int k, w, v; cout << "please input count:"; cin >> n; totv = 0; for( k = 0; k < n; k++) { cout << "please input the weight and val" << endl; cin >> arr[k].weight; cin>> arr[k].value; } cout << "please input limitw:"; cin >> limitw; maxv = 0; for(k = 0; k < n; k++) { cop[k] = 0; } find(0, 0, totv); cout << "the result is:"; for(k = 0; k < n; k++) { if(option[k]) { cout << k + 1 << " "; } } cout << endl; cout << "the total value is:" << maxv << endl; return 0; }