acwing 4. 多重背包问题 I

最新推荐文章于 2025-04-05 09:47:32 发布

After__rain

最新推荐文章于 2025-04-05 09:47:32 发布

阅读量634

点赞数

分类专栏： acwing 动态规划

本文链接：https://blog.csdn.net/qq_41567618/article/details/103638186

版权

acwing 同时被 2 个专栏收录

22 篇文章

订阅专栏

动态规划

18 篇文章

订阅专栏

本文介绍了一种解决背包问题的动态规划方法，通过实例演示了如何处理具有数量限制的物品，以最大化背包的价值。代码实现使用C++，展示了如何通过不断更新状态数组来找到最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include<bits/stdc++.h>
using namespace std;

long long n,m,f[1000005],sum=0,g=0,w[1000005],v[1000005],c[1000005];
bool judge=false;

//¿¼ÂÇÒ»²¨¶þ½øÖÆ²ð·Ö


int main(){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>w[i]>>v[i]>>c[i];
		}
			memset(f,0,sizeof(f));
			for(int i=1;i<=n;i++){
					int p=1;
					while(p<c[i]){
					for(int j=m;j>=p*w[i];j--){
						f[j]=max(f[j],f[j-p*w[i]]+v[i]*p);
						}
					c[i]-=p;	
					p=p<<1;
					}
					if(c[i]>0){
						for(int j=m;j>=c[i]*w[i];j--){
						f[j]=max(f[j],f[j-c[i]*w[i]]+v[i]*c[i]);
						}
					}
			}
			cout<<f[m]<<endl;
}