二进制优化

//
// Created by mywin on 2020/9/24.
//

#include<iostream>
#define MAX_N 107

using namespace std;

int N, V;
int v[MAX_N], w[MAX_N], s[MAX_N];
int dp[MAX_N];

void input(){
    cin >> N >> V;
    int idx = 0;
    while(idx < N){
        cin >> v[idx] >> w[idx] >> s[idx];
        idx++;
    }

}



void solve(){
    for(int i = 0; i < N; i++){
        if(s[i]*v[i] >= V){
            for(int j = v[i]; j <= V;j++)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

        }
        else{
            int k = 1;
            while(k <= s[i]){
                for(int j = V; j >= k*v[i]; j--)
                    dp[j] = max(dp[j], dp[j - k*v[i]] + k*w[i]);
               s[i] -= k;
                k *= 2;
            }
            for(int j = V; j >= s[i]*v[i]; j--)
                dp[j] = max(dp[j], dp[j - s[i]*v[i]] + s[i]*w[i]);
        }
    }

    printf("%d\n", dp[V]);
}

int main(){
    input();
    solve();
    return 0;
}