A30907 题解

#include<iostream>
using namespace std;
const int N = 100010;
const int M = 900010;
int dp[M],w[N],v[N],f[N];  
int main(){
    int n,m,sum;
    cin>>m>>n;
    for (int i = 1; i <= n; i++) {
        cin>>w[i]>>v[i]>>sum;
        if(sum != 0){
            f[i] = min(sum,m / w[i]);
        }else{
            f[i] = m / w[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= f[i]; k++) {
            for (int j = m; j >= 0; j--) {
                if (j >= w[i]) {
                    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
                }
            }
        }
    }
    cout<<dp[m];
    return 0;
}