题题题题题解

本质就是多重背包问题，套模板即可

#include <bits/stdc++.h>
using namespace std;
int cost[1145140], value[1145140], max_c[1145140], dp[1145140];

int main(){
    int m, n;
    cin >> m >> n;
    for(int i=1;i<=n;++i){
        cin >> cost[i] >> value[i] >> max_c[i];
        if(max_c[i]==0) max_c[i] = m/cost[i];
        else max_c[i] = min(max_c[i], m/cost[i]);
    }
    for(int i=1;i<=n;++i){
        for(int k=1;k<=max_c[i];++k){
            for(int j=m;j>=cost[i];--j){
                dp[j] = max(dp[j], dp[j-cost[i]]+value[i]);
            } 
        } 
    } cout << dp[m];
}