动态规划——多重背包
多重背包区别于01背包和完全背包的关键是，物品的个数一定。 但它们的状态方程还是一样的，对于多次背包问题，我们可以把他转换成01背包问题，但是要注意优化，因为当数据量比较大的时候，容易费时，即时间复杂度太高，需要进行优化。 我们先把之前的状态方程在· f[i][j]表示从i个物品中选取体积不超过j物品的最大价值。 f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,........,f[i-1][j-kv]+kw),kv<j。 这时读者朋友可能会想可不可以像完全背包那样，进行状态方程的转换。emmm，答案是：不可以的，不信的话可以自己尝试转换一下。 下面我们用01背包的思想去解决该问题，对于i个物品有k个，价值为w；那么我们可不可以把它这样理解：我们把这些物品都看成不一样的，再仔细想一下，这不就变成01背包了吗？但是时间太慢了，我们优化一下。 这里的优化为二进制优化 我们把这k个物品进行分割处理， 分为1，2，4，8，16………。只要保证其和大于k就可以。 为什么空2进制来优化呢，因为可以减少时间复杂度，其他0到k之中的任意一个数都可以由分割的二进制数进行组合而成。 例如：k为25，下面进行分割 1，2，4，8，16.怎么分割的呢？ 先是1，那么还剩24 2，22 4，28 8，20 16，4 4，0//剩余的自己组成一个 剩下就是01背包了，注意此时不再有i个物品了，而是变成了转换以后的物品个数。
多重背包
代码：
cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int V,m;
cin>>V>>m;
int sum=0,a,b,c;
vector<int> v,w;
v.push_back(0);
w.push_back(0);
for(int i=1;i<=m;++i)
{
cin>>a>>b>>c;
int k=1;
while(k<=a)
{
v.push_back(b*k);
w.push_back(c*k);
a-=k;
k*=2;
}
if(a>0)
{
v.push_back(b*a);
w.push_back(c*a);
}
}
vector<int> f(V+1);
for(int i=1;i<v.size();++i)
{
for(int j=V;j>=v[i];--j)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[V]<<endl;
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-05-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
