分组背包问题有 N 组物品和一个容量是 V 的背包。每组物品有若干个同一组内的物品最多只能选一个。每件物品的体积是 vij价值是 wij其中 i 是组号j 是组内编号。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行有两个整数 NV用空格隔开分别表示物品组数和背包容量。接下来有 N 组数据每组数据第一行有一个整数 Si表示第 i 个物品组的物品数量每组数据接下来有 Si 行每行有两个整数 vij,wij用空格隔开分别表示第 i 个物品组的第 j 个物品的体积和价值输出格式输出一个整数表示最大价值。数据范围0N,V≤1000Si≤1000vij,wij≤100输入样例3 5 2 1 2 2 4 1 3 4 1 4 5输出样例8import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N110; static int v[][]new int[N][N]; static int w[][]new int[N][N]; static int f[][]new int[N][N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int mInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { int rInteger.parseInt(br.readLine()); v[i][0]r;w[i][0]r; for (int j 1; j r; j) { stnew StringTokenizer(br.readLine()); w[i][j]Integer.parseInt(st.nextToken()); v[i][j]Integer.parseInt(st.nextToken()); } } //定义f[i][j]为在前i组物品里面选 背包容量不超过j的最大价值 for (int i 1; i n; i) { for (int j 1; j m; j) { f[i][j]f[i-1][j];//第i组物品什么也不选 for (int k 1; k w[i][0]; k) {//是否选第i组内的第k个物品 if(jw[i][k])f[i][j]Math.max(f[i][j], f[i-1][j-w[i][k]]v[i][k]); } } } bw.write(f[n][m]); br.close(); bw.flush(); bw.close(); } }有依赖的背包问题有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系且依赖关系组成一棵树的形状。如果选择一个物品则必须选择它的父节点。如下图所示如果选择物品5则必须选择物品1和2。这是因为2是5的父节点1是2的父节点。每件物品的编号是 i体积是 vi价值是 wi依赖的父节点编号是 pi。物品的下标范围是 1…N。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行有两个整数 NV用空格隔开分别表示物品个数和背包容量。接下来有 N 行数据每行数据表示一个物品。第 i 行有三个整数 vi,wi,pi用空格隔开分别表示物品的体积、价值和依赖的物品编号。如果 pi−1表示根节点。数据保证所有物品构成一棵树。输出格式输出一个整数表示最大价值。数据范围1≤N,V≤1001≤vi,wi≤100父节点编号范围内部结点1≤pi≤N;根节点 pi−1;输入样例5 7 2 3 -1 2 2 1 3 5 1 4 7 2 3 6 2输出样例11import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N110; static int v[]new int[N]; static int w[]new int[N]; static int f[][]new int[N][N]; //f[u][j]表示以u为根的子树中 最大容量为j时 的最大价值 static int n,m; static int id1; static int h[]new int[N]; static int e[]new int[N]; static int ne[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); mInteger.parseInt(st.nextToken()); int root-1; for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); w[i]Integer.parseInt(st.nextToken()); v[i]Integer.parseInt(st.nextToken()); int pInteger.parseInt(st.nextToken()); if(p-1)rooti; else add(p,i); } dfs(root); bw.write(f[root][m]); br.close(); bw.flush(); bw.close(); } static void dfs(int u){ //先把根节点放入 for (int i w[u]; i m; i) { f[u][i]v[u]; } //其实相等于是分组背包问题 for (int i h[u]; i 0; ine[i]) {//枚举每一棵子树 相当于枚举每个组 int sone[i]; dfs(son); for (int j m; j w[u]; j--) {//枚举体积 体积至少要保证能装下父节点 //相当于枚举背包体积 要从大往小 for (int k 0; kw[u] j; k) {//枚举决策 相当于枚举选组内的哪个 f[u][j]Math.max(f[u][j], f[u][j-k]f[son][k]); } } } } static void add(int a,int b){ e[id]b; ne[id]h[a]; h[a]id; } }