题解 | 【模板】分组背包

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int n , M;
    cin>>n>>M;

    map<int,vector<pair<int,int>>> things;

    for(int i = 0 ; i < n ; i++){
        int w,v,g;
        cin>>w>>v>>g;

        things[g].push_back({w,v});
    }

    vector<vector<int>> dp(things.size()+1,vector<int>(M+1,0));

    for(int i = 1 ; i <= things.size() ; i++){
        for(int j = 0 ; j <= M ; j++){

            dp[i][j] = dp[i-1][j];
            
            for(auto& thing : things[i]){

                if(j < thing.first){
                    continue;
                }
                dp[i][j] = max(dp[i][j] , dp[i-1][j - thing.first] + thing.second);
            }


        }
    }


    cout<<dp[things.size()][M]<<endl;
}