Acwing 4. 多重背包问题

4. 多重背包问题 I - AcWing题库

有 (N) 种物品和一个容量是 (V) 的背包。

第 (i) 种物品最多有 (s_i) 件，每件体积是 (v_i)，价值是 (w_i)。

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

暴力法:

定义 (f[i][j]) 为遍历到第 (i) 个物品，且体积不超过 (j) 的时候获得的最大价值。

(f[i][j] = max(f[i - 1][j],f[i -1][j - v] + w,f[i - 1][j - 2 * v] + 2 * w ,...,f[i - 1][j - s_i * v] + s_i))

通过第一层for遍历物品，第二层for遍历体积，第三层遍历选法就可以得到结果了，但这样做的时间复杂度是时间复杂度是(O(物品数*背包的体积*选法)) = (O(500 * 6000 * 10)=O(1e7))，在时间复杂度内。

实现

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 6005;
int dp[N], n, m;
int main()
{
    scanf("%d%d", &n, &m);
    // 遍历物品
    while (n--)
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        // 遍历体积
        for (int i = m; i >= v; i--)
            // 遍历选法
            for (int j = 0; j <= s && v * j <= i; j++)
                dp[i] = max(dp[i], dp[i - j * v] + j * w);
    }
    printf("%d", dp[m]);
    return 0;
}