1.递归写法
//递归方法
int Knapsack(vector<int> w, vector<int> v, int i, int j, int n)
{
if (i == n) //只有一个物品
{
return j >= w[i] ? v[i] : 0;
}
else
{
if (j < w[i]) //不装
return Knapsack(w, v, i + 1, j, n);
else //装
{
int maxv1 = Knapsack(w, v, i + 1, j, n);
int maxv2 = Knapsack(w, v, i + 1, j - w[i], n) + v[i];
return maxv1 > maxv2 ? maxv1 : maxv2;
}
}
}
int main()
{
const int n = 5;
const int c = 10;
vector<int> w = { 0,2,2,6,5,4 };
vector<int> v = { 0,6,3,5,4,6 };
int maxv = Knapsack(w, v, 1, c, n);
cout << maxv << endl;
return 0;
}
2.非递归写法(从头开始缩减规模)
是从下往上填充的，m[1][c]是最大值
3.非递归写法(从后开始缩减规模)
是从上往下填充的，m[n][c]是最大值
根据下表，如何判断出都装了哪几个物品？
答案：先看m[4][10]和m[5][10]，它们的值不一样，说明5号这个物品放进去了，根据公式可以看出，如果没有放进去那么m[i][j]的值应该等于m[i-1][j]的值，5号物品的重量是4，用10-4=6，5号物品的价值是6，15-6=9，所以就到了m[4][6]，然后比较m[4][6]和m[3][6]是否一样，相等说明4号物品没有放进去，然后比较m[3][6]和m[2][6]是否相等，相等说明3号物品没有放进去，然后比较m[2][6]和m[1][6]是否相等，不等，说明2号物品放进去了，2号物品重量为2，6-2=4，价值为3，9-3=6，然后就到了m[1][4]的位置，m[1][4]和m[0][4]比较，不相等，说明1号也放进去了，所以是1、2、5号物品放进去了
