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;
}