01背包问题表示如下

有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。
问：如何向背包装物体才能使背包中物体的总价值最大？

为什么不用贪心？

我在第一次做这个题目时考虑的是贪心算法。所谓贪心问题，就是每一步决策都采取最优解，按照此方案最后结果也是最优解。
为什么这个问题不能用贪心呢？
举个例子
我的背包容量为10，而且有4个物体，它们的体积和价值分别为
w1 = 8, v1 = 9
w2 = 3, v2 = 3
w3 = 4, v3 = 4
w4 = 3, v4 = 3
贪心是每一步采取最优拿法，即每一次都优先拿价值与体积比值最大的物体
c1 = v1/w1 = 1.125（最大）
c2 = v2/w2 = 1
c3 = v3/w3 = 1
c4 = v4/w4 = 1
所以优先拿第一个物体，随后背包再也装不下其他物体了，则最大价值为9。
但是这个问题的最优解是取物体2，3，4装进背包，最大价值为3+4+3=10！！！
所以这个问题不可以用贪心法来处理。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 20010;
int w[35], v[35];
int m, n;
int f[N];

int main()
{
    while (cin >> m)
    {
        memset(w, 0, sizeof(w));
        memset(v, 0, sizeof(v));
        memset(f, 0, sizeof(f));
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> v[i] >> w[i];

        for (int i = 1; i <= n; i++)
            for (int j = m; j >= v[i]; j--)
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        cout << f[m] << endl;
    }
    return 0;
}