acwing-2. 01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

方法一：

f(i, j)表示背包容量 j 选前 i 个物品得到的最大价值，于是有

f(i, j) = max(f(i-1, j), f(i-1, j-v)+w)

#include 

using namespace std;

const int N = 1010;
int n, v;
typedef pair PII;
PII a[N];
int f[N][N];

int main() {
    int x, y;
    scanf("%d%d", &n, &v);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &a[i].first, &a[i].second);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= v; ++j) {
            f[i][j] = f[i-1][j]; // 不偷，只拿前i-1件
            if (a[i].first <= j)
                f[i][j] = max(f[i][j], a[i].second + f[i-1][j-a[i].first]); // 偷
        }
    }
    printf("%d", f[n][v]);
}

方法二：

方法一中，f[i]只依赖于f[i-1]，所以直接把第一维拿掉，同时第二层循环要从v开始，有点trivial

#include 

using namespace std;

const int N = 1010;
int n, v;
typedef pair PII;
PII a[N];
int f[N];

int main() {
    int x, y;
    scanf("%d%d", &n, &v);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &a[i].first, &a[i].second);

    for (int i = 1; i <= n; ++i) {
        for (int j = v; j >= 1; --j) {
            if (a[i].first <= j)
                f[j] = max(f[j], a[i].second + f[j-a[i].first]); // 偷
        }
    }
    printf("%d", f[v]);
}