P1776 宝物筛选

Kitason · 2022-02-13 16:43:50 · 个人记录

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,w[100005],v[100005],cnt=0,f[100005];
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        for(ll j=1;j<=c;j<<=1){
            w[++cnt]=a*j;
            v[cnt]=b*j;
            c-=j;
        }//将c件分成1,2,4,8 等 2的次幂 与 余下部分
        if(c){
            w[++cnt]=a*c;
            v[cnt]=b*c;
        }
    }
   //多重背包转化为01背包
    for(ll i=1;i<=cnt;i++){
        for(ll j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
         //滚动数组优化空间
        }
    }
    printf("%lld",f[m]);
    return 0;
}