题解

#include <bits/stdc++.h>
using namespace std;
int dp[900001],w[100001],c[100001],num[100001];
int main(){
    int n,m,sum = 0;
    cin >> m >> n;
    for(int i = 1;i <= n;i++){
        cin >> w[i] >> c[i] >> sum;
        if(sum == 0){
            num[i] = m/ w[i];
        }else{
           num[i] = min(sum,m / w[i]); 
        }
    }
    for(int i = 1;i <= n;i++){
        for(int k = 1;k <= num[i];k++){
            for(int j = m;j >= 0;j--){
                if(j >= w[i]){
                    dp[j] = max(dp[j],dp[j - w[i]] + c[i]);
                } 
            } 
        } 
    }
    cout << dp[m];
    return 0;
}