算法1

(二进制优化)

Java 代码

import java.util.ArrayList;
import java.util.Scanner;

class Good {
    int v, w;
    public Good(int v, int w) {
        this.v = v;
        this.w = w;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] f = new int[V + 1];
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] s = new int[N + 1];
        for (int i = 0; i < N; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }
        ArrayList<Good> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int k = 1; k <= s[i]; k *= 2) {
                s[i] -= k;
                list.add(new Good(v[i] * k, w[i] * k));
            }
            if (s[i] > 0) list.add(new Good(v[i] * s[i], w[i] * s[i]));
        }
        for (Good good : list) {
            for (int j = V; j >=good.v ; j--) {
                f[j] = Math.max(f[j],f[j-good.v]+good.w);
            }
        }
        System.out.println(f[V]);
    }
}