47 lines
776 B
C++
47 lines
776 B
C++
#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;
|
||
}
|
||
|
||
|