01背包模板

#define  X first
#define  Y second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int Maxn=50005;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
int dp[Maxn];
void (int c,int w,int v)
{
	for(int i=c;i<=v;i++)
		dp[i]=max(dp[i],dp[i-c]+w);
}
int ZeroOnepack(int c,int w,int v)
{
	for(int i=v;i>=c;i--)
		dp[i]=max(dp[i],dp[i-c]+w);
}
void MultiplePack(int c,int w,int p,int v)
{
	if(c*p>=v){//如果大于 就是完全背包了
		completePack(c,w,v);
		return ;
	}
	for(int k=1;k<p;k<<=1)//二进制 进行选择 可以覆盖全部
	{
		ZeroOnepack(k*c,k*w,v);
		p-=k;
	}
	ZeroOnepack(c*p,w*p,v);//最后选择总的
}
struct node{
	int c,w,p;
}a[Maxn];
int main()
{
	int n,v;
	scanf("%d%d",&n,&v);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i].c,&a[i].w,&a[i].p);
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
		MultiplePack(a[i].c,a[i].w,a[i].p,v);
	printf("%d",dp[v]);
	return 0;
}