例题

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品占用的容量是 C[i] ，得到的价值是 W[i] 。求解将哪些物品装入背包可使价值总和最大。

思路

物品仅有两种状态，即放与不放。

如果不放第 i 件物品，那么最大价值为 F[i - 1,v] ；如果放第 i 件物品，那么价值就是 F[i - 1,v - C[i]] 再加上通过放入第 i 件物品获得的价值 W[i] 。

$$F[i,v] = \max {F[i - 1,v],F[i - 1,v - C_i ] + W_i }$$

代码

#include<iostream>

using namespace std;
const int maxn = 1000;

int main() {
    int m[maxn][maxn];
    int w[maxn], v[maxn];
    int C, N;
    cin >> N >> C;
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            if (j < w[i])
                m[i][j] = m[i - 1][j];
            else
                m[i][j] = max(m[i - 1][j], m[i - 1][j - v[i]] + w[i]);
        }
    }
    int max2 = m[1][1];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            if (m[i][j] > max2) { max2 = m[i][j]; }
        }
    }
    cout << max2 << endl;
    return 0;
}

优化

如果以递减顺序计算时，可以保证在计算 F[i,v] 时能够取用 F[i - 1,v] 和 F[i - 1,v - C[i]] 的值。因此可以缩减空间占用量。

$$F[v] = \max {F[v],F[v - C_i ] + W_i }$$