多重背包问题

import java.util.*;

public class Main {
    static final int N = 510, M = 6010;
    static int[][] f = new int[N][M];
    static int[] v = new int[N], w = new int[N], s = new int[N];
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] str = sc.nextLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        for (int i = 1; i <= n; i++) {
            str = sc.nextLine().split(" ");
            v[i] = Integer.parseInt(str[0]);
            w[i] = Integer.parseInt(str[1]);
            s[i] = Integer.parseInt(str[2]);
        }

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

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

优化一维

发现在更新f[i][j]时也是只使用上一层的数据
f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

因此可以采用01背包的优化方式

import java.util.*;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] str = sc.nextLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        for (int i = 1; i <= n; i++) {
            str = sc.nextLine().split(" ");
            int v = Integer.parseInt(str[0]), w = Integer.parseInt(str[1]), s = Integer.parseInt(str[2]);

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

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