二进制多重背包

第一种:

#include<bits/stdc++.h>
using namespace std;
int tot,n,c;
int d[1005],a[11005],m[11005],w[11005],m1[11005],w1[11005],p[11005];
void put(int a0,int m0,int w0){
	int i=1;
	while(a0>d[i]){
		a0-=d[i];
		tot++;
		m1[tot]=d[i]*m0;
		w1[tot]=d[i]*w0;
		i++;
	}
	tot++;
	m1[tot]=a0*m0;
	w1[tot]=a0*w0;
}
int main(){
	tot=0;
	cin>>n>>c;
	d[1]=1;
	for(int i=2;i<=15;i++) d[i]=d[i-1]*2;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>m[i]>>w[i];
		put(a[i],m[i],w[i]);
	}
	for(int i=1;i<=tot;i++)
		for(int j=c;j>=m1[i];j--) p[j]=max(p[j],p[j-m1[i]]+w1[i]);
	cout<<p[c];
	return 0;
}

第二种:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int s,v,w;
		cin>>s>>w>>v;
		for(int j=1;j<=s;j*=2){
			for(int k=m;k>=j*w;k--) 
				dp[k]=max(dp[k],dp[k-j*w]+j*v);
			s-=j;
		}
		if(s){
			for(int k=m;k>=s*w;k--) 
				dp[k]=max(dp[k],dp[k-s*w]+s*v);
		}
	}
	cout<<dp[m];
	return 0;
}