写于2017/11/17
1、问题描述
有m件物品，它们的重量分别是W1,W2,…,Wm，它们的价值分别是V1,V2,…,Vm，现在给你个承重为n的背包，如何让背包里装入的物品具有最大的价值总和？
2、解题思路
典型的动态规划问题。
为什么叫01背包，是这m件物品，只有两种状态，可以装入和没有装入。
解决01背包问题，只需要一个方程就可以。
f[i,j]=max{f[i-1][j-wi](j>=wi)+v[j],f[i-1][j]}在上面方程中，f[i,j]表示，前i件物品中拿若干件放入容量为j的背包中的最大价值。
由于我们的数组下标都是从0开始的，所以默认初始化时，
f[0][j]=0，这个意思是说，当没有物品放入时，不管背包容量多少，其最大价值为0；
f[i][0]=0，当背包容量为空时，不管从前i件物品中怎么取，最大价值也还是0。
然后就是对最大价值方程进行动态规划。当已知f[i-1][j]时，即已知在前i-1件物品放入j容量背包的最大价值，那f[i][j]如何求呢？
首先，判断物品i的重量是否超过目前背包额重量j，如果超过，则这个物品i放不进去背包，则f[i][j]=f[i-1][j]。
如果没有超过，则尝试把背包中的重量去掉物品i的重量wi，去掉后，f[i-1][j-wi]的表示前i-1件物品在背包容量为j-wi下的最大价值，此时如果放入物品i，则价值就会变为f[i-1][j-wi]+vi，如果这个价值超过了f[i-1][j]，此时可以更新f[i][j]=f[i-1][j-wi]+vi，否则f[i][j]=f[i-1][j]，这就是前面开始说的那个那个方程。f[i,j]=max{f[i-1][j-wi](j>=wi)+v[j],f[i-1][j]}
可以用表来说明。
假如有编号为a,b,c,d,e的五件物品，重量分别是4,5,6,2,2，价值分别是6,4,5,3,6，背包的承重为10，如何让背包里装入的物品具有最大的价值？
上面遍历的过程如下，依次先从上往下，再从左往右，红色框中是初始化的0。
例如当背包容量为6，到d物品放入时，d物品的重量为2，小于背包容量6，所以d物品可以放入，如果d物品放入，则为d物品之前，容量为6-2时的最大价值加上物品d的价值，即c行4列的6+物品d的价值3，得到的最大价值为9，而这个9比之前的6（c行6列）大，进行更新。
3、代码
#include <iostream>
#include <vector>
using namespace std;
#if 1
#define max(a,b)(a>b?a:b)
class bag
{
public:
int maxweight(int n,int m,vector<int>weight,vector<int>value)
{
vector<vector<int>>v(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++)
v[i][0] = 0;
for (int i = 0; i <= n; i++)
v[0][i] = 0;
for (int i = 1; i <= n;i++)
{
for (int j = 1; j <= m;j++)
{
if (weight[j - 1] > i)
v[j][i] = v[j - 1][i];
else
v[j][i] = max(v[j - 1][i], v[j - 1][i - weight[j - 1]] + value[j - 1]);
}
}
return v[m][n];
}
};
int main()
{
int n = 10, m = 5;
vector<int>weight = { 4, 5, 6, 2, 2 };
vector<int>value = { 6, 4, 5, 3, 6 };
bag b;
cout << b.maxweight(n, m, weight, value) << endl;
system("pause");
return 0;
}
#else
#endif