抽象出过程
JAVA 代码
import java.io.*;
import java.util.*;
public class Main {
// 01背包问题
public static void ZeroOnePack(int[] dp, int v, int w, int m) {
for (int j = m; j >= v; j--) {
dp[j] = Math.max(dp[j], dp[j-v] + w);
}
}
// 完全背包问题
public static void CompletePack(int[] dp, int v, int w, int m) {
for (int j = v; j <= m; j++) {
dp[j] = Math.max(dp[j], dp[j-v]+w);
}
}
// 多重背包问题
public static void MultiplePack(int[] dp, int v, int w, int s, int m) {
// 二进制拆分
int[] newV = new int[10]; // 2^10 = 1024, 也就是说s最多可以拆成10个,故数组容量10
int[] newW = new int[10];
int newN = 0; // 新的物品种数
for (int j = 1; j <= s; j *= 2) {
newV[newN] = j * v; // 体积
newW[newN] = j * w; // 价值
s -= j;
newN++;
}
if (s > 0) {
newV[newN] = s * v;
newW[newN] = s * w;
newN++;
}
for (int i = 0; i < newN; i++) {
for (int j = m; j >= newV[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-newV[i]]+newW[i]);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品种数
int m = sc.nextInt(); // 背包容积
int[] dp = new int[m+1];
for (int i = 0; i < n; i++) {
int v, w, s;
v = sc.nextInt();
w = sc.nextInt();
s = sc.nextInt();
if (s == -1) { // 01背包问题
ZeroOnePack(dp, v, w, m);
} else if (s == 0) { // 完全背包问题
CompletePack(dp, v, w, m);
} else { // 多重背包问题
MultiplePack(dp, v, w, s, m);
}
}
System.out.println(dp[m]);
}
}