ProgramAlgTrain/20240919/CSP常考算法模板/背包问题_多重.cpp

#include <bits/stdc++.h>
using namespace std;

int v[10001],w[10001];
int f[6001];
int n,m,n1;

/*
【输入样例】
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
【输出样例】
1040

*/
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x,y,s,t=1;
        scanf("%d%d%d",&x,&y,&s);
        while (s>=t) {
            v[++n1]=x*t;          //相当于n1++;  v[n1]=x*t;
            w[n1]=y*t;
            s-=t;
            t*=2;
        }
        //把s以2的指数分堆：1，2，4，…，2^(k-1)，s-2^k+1,
        if(s>0) {
            v[++n1]=x*s;
            w[n1]=y*s; 
		}
   	}
   	
   	for(int i=1;i<=n1;i++)
        for(int j=m;j>=v[i];j--)
           f[j]=max(f[j],f[j-v[i]]+w[i]); 
    printf("%d\n",f[m]);
    
    return 0;
}