Luogu-P1776-宝物筛选_NOI导刊2010提高（02）.md

title: Luogu P1776 宝物筛选_NOI导刊2010提高（02） categories: 多重背包 tags: [编程,背包] date: 2019-06-07 20:12:00

#include <iostream>
#include <vector>

using namespace std;

int N,M;
int f[100000];


int main()
{
    cin>>N>>M;
    int t1,t2,t3,bin;
    for(int i = 1;i<=N;i++){
        cin>>t1>>t2>>t3;
        bin = 0;
        for(int j = t3;j>=1;){
            if(bin == 0){
                bin = 1;
                j -= bin;
            }
            else if(j - (bin<<1)<1){
                bin = j;
                j = 0;
            }else {
                bin <<= 1;
                j -= bin;
            }
            for(int k = M;k >= t2 * bin;k--){
                //cout<<bin<<"<-bin\n";
                 f[k] = max(f[k],f[k - t2*bin]+t1 * bin);
            }

        }
    }
    cout<<f[M];
    return 0;
}