背包

01背包

public static void zeroOne(int[] weight, int[] value, int capacity){
    dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int j = capacity; j >= weight[i]; j--) {
            if (j - weight[i] >= 0) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    }
}

完全背包

public static void complete(int[] weight, int[] value, int capacity){
    dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int j = weight[i]; j <= capacity; j++) {
            dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j]);
        }
    }
}

多重背包

public static void multi(int[] weight, int[] value, int[] nums, int capacity){
    dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int j = capacity; j >= weight[i]; j--) {
            for (int k = 0; k <= nums[i] && k * weight[i] <= j; k++) {
                dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }
}

多重背包（二进制优化）

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

    int[] weight = new int[n * 11];
    int[] val = new int[n * 11];
    int cnt = -1;
    for (int i = 0; i < n; i++) {
        s = br.readLine().split(" ");
        // 二进制优化
        int w = Integer.parseInt(s[0]);
        int v = Integer.parseInt(s[1]);
        int num = Integer.parseInt(s[2]);
        int k = 1;
        while (k <= num){
            cnt++;
            weight[cnt] = w * k;
            val[cnt] = v * k;
            num -= k;
            k *= 2;
        }
        if (num > 0){
            cnt++;
            weight[cnt] = w * num;
            val[cnt] = v * num;
        }
    }

    multi(weight, val, capacity);

    System.out.println(dp[capacity]);
}

public static void multi(int[] weight, int[] value, int capacity){
    dp = new int[capacity + 1];

    for (int i = 0; i < weight.length; i++) {
        for (int j = capacity; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}

混合背包

private static void all(int[] weight, int[] value, int[] type, int capacity) {
    dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        // 只能一次，01背包
        if (type[i] == -1) {
            for (int j = capacity; j >= weight[i]; j--) {
                if (j - weight[i] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        // 无限次，完全背包
        }else if (type[i] == 0){
            for (int j = weight[i]; j <= capacity; j++) {
                dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j]);
            }
        // 有限次，多重背包
        }else {
            for (int j = capacity; j >= weight[i]; j--) {
                for (int k = 0; k <= type[i] && k * weight[i] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
    }
}