题目描述

blablabla

样例

blablabla

算法1

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

状态表示：f(i,j)表示只考虑前i个物品，且总体积不大于j的所有选法。
状态属性：MAX

状态计算：
考虑取多少个第i个物品，划分成以下集合：
- 取0个物品：$f(i-1,j)$
- 取1个物品：$f(i-1,j-v_i)+w_i$
- 取2个物品：$f(i-1,j-2\*v_i)+2\*w_i$
- …
- 取k-1个物品：$f(i-1,j-(k-1)\*v_i)+(k-1)\*w_i$
- 取k个物品：$f(i-1,j-k\*v_i)+k\*w_i$

因此，状态转移方程就是：
$f(i,j) = max(f(i-1,j-k\*v_i) + k\*w_i)$，其中k是取第i个物品的个数。

时间复杂度

状态有$O(n^2)$种，状态转移的计算量是$O(n)$，因此整体的时间复杂度是$O(n^3)$。

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++) {
            for (int k = 0; a[i] * k <= j; k++)
                f[i][j] = max(f[i][j], f[i-1][j - k * a[i]] + k * w[i]);
        }
    }

    cout << f[n][v];

    return 0;
}

算法2

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

观察上述的状态转移方程：$f(i,j) = max(f(i-1,j-k\*v_i) + k\*w_i)$。
把等式右边展开：
$max(f(i-1,j-k\*v_i) + k\*w_i) = max(f(i-1,j), f(i-1,j-v_i)+w_i, f(i-1,j-2\*v_i)+2\*w_i, …, f(i-1,j-(k-1)\*v_i)+(k-1)\*w_i, f(i-1,j-k\*v_i)+k\*w_i)$

再来考虑$f(i,j-v_i)$的状态转移：
$f(i,j-v_i) = max(f(i-1,j-(k+1)\*v_i)+k\*w_i)$
再次把等式右边展开：
$max(f(i-1,j-(k+1)\*v_i)+k\*w_i) = max(f(i-1,j-v_i), f(i-1,j-2\*v_i)+2\*w_i, f(i-1,j-3\*v_i)+3\*w_i, …, f(i-1, j-(k+1)\*v_i)+k\*w_i)$

比较上下两个展开式可以发现：
$f(i,j) = max(f(i-1,j), f(i,j-v_i) + w_i)$
即状态转移与k无关了。

时间复杂度

状态数仍然是$O(n^2)$，状态转移从$O(n)$优化成$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];

    // f(i,j) = max(f(i-1,j), f(i,j-v_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][j - a[i]] + w[i]);
        }
    }

    cout << f[n][v];

    return 0;
}

算法3

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

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

可以采用与01背包问题一一致的优化思路，把i优化掉。
由于我们在计算j的时候，使用的是第i层的$j-v_i$，而$j-v_i < j$，因此我们可以从小到大枚举j，此时在计算j的时候，$j-v_i$已经被计算过了（与01背包问题的区别）。

时间复杂度

仍然是$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];

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

    cout << f[v];

    return 0;
}