题解 | 【模板】分组背包

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int []b=new int [101];
        int [][]w=new int [101][101];
        int [][]v=new int [101][101];
        int []z=new int [n];
        int t=0;
        int []dp=new int [m+1];
        for(int i=0;i<n;i++){
            int sw=sc.nextInt();
            int sv=sc.nextInt();
            int g=sc.nextInt();
       
            w[g][b[g]]=sw;
            v[g][b[g]]=sv;
            b[g]++;             //存取每个组的数据数量
            if(b[g]==1){
                z[t]=g;         //存取含有数据的组的位置
                t++;            //有数据的组别个数
            }
        }
        
        for(int i=0;i<t;i++){           //一组只能取一个，所以挨个遍历
            for(int j=m;j>=0;j--){          //因为不能重复选择所以逆循环
                for(int num=0;num<b[z[i]];num++){   //一个组中挨个遍历
                    if(w[z[i]][num]<=j)
                        dp[j]=Math.max(dp[j],dp[j-w[z[i]][num]]+v[z[i]][num]);
                }
            }
        }
        System.out.println(dp[m]);
    }
}