背包九讲——多重背包问题

#include<stdio.h>
int dp[6001],w[501],v[501],nums[501];//dp[i]表示背包容量为i时所获得最大价值
int n,m;
int max(int x,int y){
	return x>y?x:y;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&v[i],&w[i],&nums[i]);
	}
	for(int i=1;i<=n;i++){//枚举物品个数
		for(int j=m;j>=1;j--){//逆序枚举背包容量，01背包的扩展
			for(int k=0;k<=nums[i];k++){//枚举物品个数
				if(j>=k*v[i]){//如果背包容量大于此时物品重量
					dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);//可以选择，并且判断选还是不选最优
				}
			}
		}
	}
	printf("%d",dp[m]);
	return 0;
}

#include<iostream>
using namespace std;
int dp[1001],w[1001],c[1001];
int n,m,t;
int a,b,nums;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>nums;
		for(int j=1;j<=nums;j<<=1){//这下面就是二进制分解
			w[t]=j*a;//把num分解成1，2，4，8……乘上对应的重量和价值
			c[t++]=j*b;
			nums-=j;//分解出来就要减去
		}
		if(nums){//如果num还有剩余，让剩余的自己单独成一项
			w[t]=nums*a;
			c[t++]=nums*b;
			nums=0;//剩余的自成一项，用完了就是0了
		}
	}
	for(int i=0;i<t;i++){//下面就是01背包解法了
		for(int j=m;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
		}
	}
	printf("%d",dp[m]);
	return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e3+5,M=2e4+5;
int f[M],g[M],v[N],w[N],s[N],q[M];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	memcpy(g,f,sizeof(f));//因为要正序遍历背包容量了，复制一个f数组g，保证在遍历i+1个物品时，状态由g[i]转移过来
        cin>>v[i]>>w[i]>>s[i];
        for(int j=0;j<v[i];j++)//分解成v[i]个类
        {
            int head=0,tail=-1;
            for(int k=j;k<=m;k+=v[i])//对每个类使用单调队列，s[i]的数就是滑动窗口的宽度
            {
                if(head<=tail&&q[head]<k-s[i]*v[i])head++;//q[h]不在窗口[k-s[i]*v[i],k-v[i]]之内，在其左侧，队头要出队
                if(head<=tail)f[k]=max(g[k],g[q[head]]+(k-q[head])/v[i]*w[i]);//使用队头最大值更新f，(k-q[head])/v[i]表示还能放入的物品个数
                //f[k]通过前面的旧值g[q[head]]来更新，所以窗口在g数组上滑动，f[k]=窗口中最大值+还能放入物品的价值
                while(head<=tail&&g[k]>=g[q[tail]]+(k-q[tail])/v[i]*w[i])tail--;//当前值大于队尾值，队尾出队
                q[++tail]=k;//下标入队，便于对头出队
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}