一个物品x可以取0~m件。
那么可以简化成在
0个x，1个x，2个x，4个x。。。中取任意件
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define maxn 200000
int c[maxn];
int w[maxn];
int dp[501];
int top;
void dos(int m,int ws,int s)
{int i,ks;if(m==0)return ;for(i=1,ks=1;ks<=m;i=i*2,ks=ks+i){c[top]=i*ws;w[top++]=i*s;}ks=ks-i;i=i/2;dos(m-ks,ws,s);}
int main()
{int n,v,i,j,m,s,ws;while(~scanf("%d%d",&n,&v)){top=0;for(i=0; i<n; i++){scanf("%d%d%d",&m,&ws,&s);dos(m,ws,s);}int maxx;maxx=0;for(i=0; i<top; i++){for(j=v; j>=c[i]; j--){dp[j]=max(dp[j],dp[j-c[i]]+w[i]);maxx=max(maxx,dp[j]);}}cout<<maxx<<endl;}return 0;
}