$$\color{Red}{多重背包:庆功会(模板题)}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

证明

多重背包问题:三种语言+朴素版+强行拆01背包版

多重背包:三种语言+(迭代版和物理版)二进制分堆

本题是多重背包的模板题，直接使用朴素版代码即可ac，还可以使用二进制分堆的优化。以及单调队列的优化版。
庆功会的多重背包的三种代码复习完成，切记多重背包也是利用的i-1层的状态进行转移，所以优化一维也需要背包体积倒序。二进制分堆s -= k需要在一次新的i循环内的j循环完全结束，即把当前这个物品在所有j的情况枚举完才能减去，而且k（组数）循环应该在体积循环外，因为是分组后的01背包.

java二进制拆分

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * ClassName: Main
 * Package: PACKAGE_NAME
 * Description:
 *
 * @Author FanXY
 * @Create 2023/4/26 13:11
 * @Version 1.0
 */
public class Main {
    static int N = 6010, n, m;
    static int[] f = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            int v = Integer.parseInt(s2[0]);
            int w = Integer.parseInt(s2[1]);
            int s = Integer.parseInt(s2[2]);

            for (int k = 1; k <= s; k *= 2) {
                for (int j = m; j >= k * v; j--) 
                    f[j] = Math.max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            if(s > 0)
                for (int j = m; j >= s * v; j--) {
                    f[j] = Math.max(f[j], f[j - s * v] + s * w);
                }
        }
        System.out.println(f[m]);

    }
}

java朴素

import java.io.*;

public class Main {
    static int n, m, N = 6010;
    static int f[][] = new int[N][N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        for (int i = 1; i <= n; i++) {
            String s2[] = br.readLine().split(" ");
            int v = Integer.parseInt(s2[0]);
            int w = Integer.parseInt(s2[1]);
            int s = Integer.parseInt(s2[2]);

            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= s && k * v <= j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v] + k * w);
                }
            }
        }

        System.out.println(f[n][m]);
    }
}

朴素版

N = 510
v = [0] * N
w = [0] * N
s = [0] * N
f = [0] * int(6010)
n, m = map(int, input().split())
for i in range(1, n+1):
    v[i], w[i], s[i] = map(int, input().split())

for i in range(1, n+1):
    for j in range(m, v[i]-1, -1):
        for k in range(s[i]+1):
            if j - k * v[i] >= 0:
                f[j] = max(f[j], f[j - k * v[i]] + k * w[i])

print(f[m])