如果你觉得这篇题解对你有用,可以点个赞或关注再走呗~
背包问题:
0-1背包问题:从前 i 件物品中选且每件物品只能选择一次
完全背包问题:选多少个第 i 件物品
分组背包问题:从第i组物品组中选哪个物品(第k个物品)
分析
枚举第i组物品中选哪个
f[i][j]=f[i-1][j];
f[i][j]=Math.max(f[i][j],f[i-1][j-v[i,k]]+w[i,k])
ACcode
import java.util.*;
public class Main{
static int N=110;
static int f[][]=new int[N][N];
static int v[][]=new int[N][N];
static int w[][]=new int[N][N];
static int s[]=new int[N];
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
for(int i=1;i<=n;i++){
//输入n组
s[i]=sc.nextInt();
//表示每一组的物品个数
for(int j=1;j<=s[i];j++){
//每一组的第j件
v[i][j]=sc.nextInt();
w[i][j]=sc.nextInt();
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
//从前i-1组中选且最大体积为j
for(int k=1;k<=s[i];k++){
//选第i组的第k个数,剩下的则从前i-1个数中选
if(j>=v[i][k])f[i][j]=Math.max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
System.out.println(f[n][m]);
//输出集合的含义:从n个物品组中选体积最大为j的方案
//属性:max
}
}