题目描述

blablabla

样例

blablabla

算法1

朴素版 时间：$O(n^2)$，空间$O(n^2)$

状态表示：f(i,j)表示前i件物品在容量为j的背包中能够放下的价值。
状态属性：MAX

状态计算：
集合划分成取第i件物品和不取第i件物品两个集合
- 不取第i件物品：$f(i-1, j)$
- 取第i件物品：$f(i-1, j-vi + wi)$
状态转移：$f(i,j) = max(f(i-1,j), f(i-1,j-v_i)+w_i)$

时间复杂度

状态数为$O(n^2)$，状态计算复杂度为：$O(1)$，因此时间复杂度为：$O(n^2)$。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int a[N], w[N];
int f[N][N];

int main()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; i++) cin >> a[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= v; j++) {
            f[i][j] = f[i-1][j];
            if (j >= a[i])
                f[i][j] = max(f[i][j], f[i-1][j-a[i]] + w[i]);
        }
    }

    cout << f[n][v];

    return 0;
}

算法2

空间优化版 时间：$O(n^2)$，空间$O(n)$

观察状态转移方程：$f(i,j) = max(f(i-1,j), f(i-1,j-v_i)+w_i)$

我们在计算第i维的时候，只与第i-1维有关，因此首先可以想到使用滚动数组优化掉一维。
继续观察发现，状态j的计算只与j前面的状态有关系，因此可以只用一个数组。需要注意的是，我们更新j的状态时候需要从右到左进行更新，因为我们在计算状态j时，必须保证j左边的状态是属于i-1维，即未被更新过的。

优化后的状态转移：$f(j) = max(f(j), f(j-v_i)+w_i)$

时间复杂度

依然是$O(n^2)$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int a[N], w[N];
int f[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; i++) cin >> a[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = v; j >= a[i]; j--) {
            f[j] = max(f[j], f[j-a[i]] + w[i]);
        }
    }

    cout << f[v];

    return 0;
}