多重背包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[二进制位优化]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。