思考
1.定义状态
集合:dp[i][j] 表示选到第i组物品,容量不超过j的选法集合
含义:max
2. 状态计算
考虑最后一步, 最后一步就是选到 i组时候的操作, 以及如何用之前的状态推出这个操作的状态:
1. 不选
代表:dp[i - 1][j]
2.第i组中选一个
代表:max(dp[i - 1][j - v[k]] + w[k]), 也就是肯定选推出当作状态最大值的时候
代码
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
private static int[] readInts() throws IOException {
int[] nums = null;
String[] strs = in.readLine().trim().split(" ");
nums = new int[strs.length];
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(strs[i]);
}
return nums;
}
private static void close() throws IOException {
in.close();
out.close();
}
public static void main(String[] args) throws IOException {
int[] p1 = readInts();
//这样可能更直观点吧,不过都一样
//List<List<Pair>> lst = new ArrayList<>();
List<int[][]> lst= new ArrayList<>();
lst.add(new int[0][0]);
for (int i = 0; i < p1[0]; i++) {
int[] p2 = readInts();
int[][] temp = new int[p2[0]][2];
for (int j = 0; j < p2[0]; j++) {
temp[j] = readInts();
}
lst.add(temp);
}
int[][] dp = new int[lst.size()][p1[1] + 1];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j <= p1[1]; j++) {
int[][] nums = lst.get(i);
dp[i][j] = dp[i - 1][j];
for (int[] num: nums) {
if (j >= num[0]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - num[0]] + num[1]);
}
}
}
}
out.write(dp[p1[0]][p1[1]] + "");
close();
}
}