朴素做法

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[][] f = new int[N][N];
    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);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

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

                    f[i][j] = Math.max(t, f[i][j]);
                }
            }

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

逐步优化

完全背包

下面只考虑选择的情况

由f[i][j] = max(f[i - 1][j - 1 * v] + 1 * w, f[i - 1][j - 2 * v] + 2 * w, f[i - 1][j - 2 * v] + 2 * w, ..., f[i - 1][j - n * v] + n * w); (j >= n * v)
  f[i][j - 1 * v] =                      max(f[i - 1][j - 2 * v] + 1 * w, f[i - 1][j - 3 * v] + 2 * w, ..., f[i - 1][j - n * v] + (n - 1) * w);

发现f[i][j] = f[i][j - v] + w;
再考虑不选情况直接取最值即可

所以对于代码

    for (int k = 1; k * v[i] <= j; k++)
        t = Math.max(t, f[i - 1][j - k * v[i]] + k * w[i]);

可替换为

    t = Math.max(t, f[i][j - v[i]] + w[i]);

多重背包

可以采用二进制优化的思路，这里不进行书写

我们发现s最大只有1000，因此我们可以直接对该问题改为多重背包的二进制优化写法对于完全背包的情况把数量设为1000即可，在进行二进制优化

代码如下

import java.util.*;

public class Main {
    static final int N = 1010, M = 10 * N;
    static int[][] f = new int[M][N];
    static int[] v = new int[M], w = new int[M], s = new int[N];
    static int n, m, idx;

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

        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            int k = 1;
            if (c == -1) c = 1;
            if (c == 0) c = 1000;

            while (k <= c) {
                idx++;
                v[idx] = k * a;
                w[idx] = k * b;
                c -= k;
                k *= 2;
            }
            if (c > 0) {
                idx++;
                v[idx] = c * a;
                w[idx] = c * b;
            }
        }

        n = idx;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= v[i]) 
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }

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

化为一维

import java.util.*;

public class Main {
    static final int N = 1010, M = 10 * N;
    static int[] f = new int[N];
    static int[] v = new int[M], w = new int[M], s = new int[N];
    static int n, m, idx;

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

        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            int k = 1;
            if (c == -1) c = 1;
            if (c == 0) c = m / a + 1;直接上取整

            while (k <= c) {
                idx++;
                v[idx] = k * a;
                w[idx] = k * b;
                c -= k;
                k *= 2;
            }
            if (c > 0) {
                idx++;
                v[idx] = c * a;
                w[idx] = c * b;
            }
        }

        n = idx;
        //注：也可以边写边读
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }

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