/*
核心思路:把f[i][j] 看成前i组里面选总体积小于j的最大价值
然后划分区间:第i组里面选k个属于 ——>0到s[i]个
结果就是转移成去掉第i组第k个物品的体积v[i][k]就变成从n-1里面选最大值,因为去掉了第k个物品
所以要加上k的价值w[i][k];
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=110;
int n=sc.nextInt();
int m=sc.nextInt();
int s[]=new int[N];
int v[][]=new int[N][N];
int w[][]=new int[N][N];
int f[]=new int[N];
for(int i=1;i<=n;i++){
s[i]=sc.nextInt();
for(int j=1;j<=s[i];j++){
v[i][j]=sc.nextInt();
w[i][j]=sc.nextInt();
}
}
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=0;k<=s[i];k++)
if(j>=v[i][k]) f[j]=Math.max(f[j],f[j-v[i][k]]+w[i][k]);
System.out.println(f[m]);
}
}
二刷复习(分组背包):
将最后一层循环当成遍历每一组内的元素,取其中的最大值
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 110;
int n = sc.nextInt();
int m = sc.nextInt();
int f[] = new int[N];
for(int i = 1; i <= n; i ++){
int s = sc.nextInt();
int v[] = new int[N];
int w[] = new int[N];
for(int j = 1; j <= s; j ++){
v[j] = sc.nextInt();
w[j] = sc.nextInt();
}
for(int j = m; j >= 0; j --){ // 一维优化
for(int k = 0; k <= s; k ++){
// 遍历第i组选第k个的最大价值,k=0表示第i组不选 = f[i-1][j-0]+0
if(v[k] <= j) f[j] = Math.max(f[j], f[j - v[k]] + w[k]);
}
}
}
System.out.println(f[m]);
}
}