多重背包2[二进制位优化]

本文主要是介绍多重背包2[二进制位优化]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据范围加强一下

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

这时候$O(n^3)$的算法不行，需要优化成$O(N\ast logs\ast V)$
思想
多重背包拆成01背包，并且使用二进制优化。
多重背包是每个物品可以选$s_i$次，把多重背包问题拆成$\Sigma s_i$ 个01背包问题,拆成$\Sigma s_i$ 个实际上复杂度并没有优化。在拆的时候有技巧，不能拆成很多1的组合，我们想最少拆成多少份，拆成$num=\lceil lo{g}_2\Sigma s_i\rceil$份(上取整)。

比如 第i件物品有13件，拆成$\lceil lo{g}_{2}13\rceil =4$份,分别是1，2，4，6
其中6的来源是13-(1+2+4)=6，即尽可能拆分成2的倍数，其余为作差取得。

对于拆出来的num个01背包问题，其中物品体积和价值需要乘以拆出来的系数。

这里的拆分我们使用vector进行维护，拆好一个加入动态数组一个。

多重背包拆分成为01背包的代码

for(int i=0;i<n;i++){//n表示多重背包的个数cin>>v>>w>>s;for(int k=1;k<=s;k*=2){//拆分成01背包 ，二进制优化s-=k;goods.push_back({k*v,k*w});//物品的体积和价值相应的扩大k倍}if(s>0){goods.push_back({s*v,s*w});}}

ac代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=2010;
int n,m,v,w,s; 
int f[maxn];struct Goods{int v,w;
};
int main(){vector<Goods> goods;cin>>n>>m;for(int i=0;i<n;i++){cin>>v>>w>>s;for(int k=1;k<=s;k*=2){//拆分成01背包 s-=k;goods.push_back({k*v,k*w});}if(s>0){goods.push_back({s*v,s*w});}}memset(f,0,sizeof(f));for(int i=0;i<goods.size();i++){for(int j=m;j>=goods[i].v;j--){f[j]=max(f[j],f[j-goods[i].v]+goods[i].w);}}cout<<f[m]<<endl;goods.clear();return 0;
}

这篇关于多重背包2[二进制位优化]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---