P1776 宝物筛选 (多重背包二进制拆分)

题目描述:

题目传送门


解题思路:

根据题意知此题为多重背包裸题,即每个物品至多可以选 m m m 次的背包题目。

世上背包千千万,无一不是 01 01 01 背包的变体,多重背包亦是如此。
**若第 i i i 个物品的数目为 m i m_i mi​ ,我们可以将一种物品视作 m i m_i mi​ 个物品,第 j j j 个物品的重量以及价值都是原物品的 j j j 倍。**在此基础上我们可以直接进行 01 01 01 背包。

for (int i=1;i<=n;i++)  //枚举物品种数
  for (int j=V;j>=w[i];j--)  //枚举背包承重量
    for (int k=1;k<=m[i]&&k*w[i]<=j;k++)  //枚举选取单个物品的数量
      f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);  //转移

同样,我们亦可将每种物品至多选 m m m 次视作单种物品存在 m m m 个,这样总物品数就变成了 ∑ i = 1 n m i \sum_{i=1}^{n} m_i ∑i=1n​mi​。

cnt=0;
for (int i=1;i<=n;i++)
  {
    cin>>a>>b>>m[i];  //输入单个物品的价值,重量,个数
    for (int j=1;j<=m[i];j++)
      {
        cnt++;
        v[cnt]=a;  //视作 m 个物品依次存好
        w[cnt]=b;
      }
  }

这确实是多重背包裸的解法,但是本题的数据规模有亿点大,所以我们考虑在多重背包的思路上加亿点优化。
普遍优化多重背包的方法有两种

  1. 单调队列
  2. 二进制

这里我们选择用二进制优化。

二进制拆分:

普遍处理多重背包的办法就是对物品数 m i m_i mi​ 进行如下转换:

物品数:18 \\序列一
转换为:1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 //序列二
意思是把一个数量为 18 18 18 的物品转换为 18 18 18 个数量为 1 1 1 的物品,然后01背包。

我们观察两个序列,能够发现,序列一与序列二之所以能够互换,是因为序列二中的元素可以构成任何一个序列一中的元素,也就是说 18 18 18 个 1 1 1 可以构成 1 ⋯ 18 1\cdots 18 1⋯18 的所有数字。
也就是说,我们只需要构造出一个可以组成 1 ⋯ 18 1\cdots 18 1⋯18 中所有数字的序列三,并使它的长度尽量的短,就形成了优化。
这里要用到一个大家耳熟能详的原理,二进制拆分。即每一个整数都能表示成一组不出现重复的二的整数次幂的和
也就是说, 1 ⋯ 18 1\cdots 18 1⋯18 中的数字可以由 2 0 ⋯ 2 3 , ( 18 − 2 4 + 1 ) 2^0\cdots 2^3,(18-2^4+1) 20⋯23,(18−24+1) 来构成,即构成 1 ⋯ 18 1\cdots 18 1⋯18 的最短序列三为1,2,4,8,3

若要构成 1 ⋯ n 1\cdots n 1⋯n 的所有数字,设 p p p 表示 2 0 + 2 1 + 2 2 + ⋯ + 2 p < = n 2^0+2^1+2^2+\cdots +2^p<=n 20+21+22+⋯+2p<=n 的最大 p p p,我们亦能够用 2 0 ⋯ 2 p , ( n − 2 p + 1 + 1 ) 2^0\cdots 2^p,(n-2^{p+1}+1) 20⋯2p,(n−2p+1+1) 来构成序列三,选取序列三的数加起来可以得到任何一个小于 n n n 的正整数。

可以证明这种二的整数次幂的序列的长度为 l o g n log_n logn​ ,是所有能构成 1 ⋯ n 1\cdots n 1⋯n 的序列中最短的。

我们亦能用这种办法表示所有物品的可选数目:

2 0 ∗ w i , 2 1 ∗ w i , 2 2 ∗ w i ⋯ 2 p ∗ w i , ( n − 2 p + 1 + 1 ) ∗ w i 2^0*w_i,2^1*w_i,2^2*w_i\cdots 2^p*w_i,(n-2^{p+1}+1)*w_i 20∗wi​,21∗wi​,22∗wi​⋯2p∗wi​,(n−2p+1+1)∗wi​

通过这个序列,我们可以构造出所有小于 w i ∗ m i w_i*m_i wi​∗mi​ 的可被 w i w_i wi​ 整除的数,也就可以构成取物品的每种方案。

明白了这种二进制拆分优化,我们可以最少的数字来构造出选择物品的数目,原本需要枚举 n n n次,现在仅需 l o g n log_n logn​ 次,大大提高了算法效率。


CODE:

#include <bits/stdc++.h>
using namespace std;
int n,V,a,b,v[1000010]={0},w[1000010]={0},m,cnt=0;
int f[10000010]={0};
int main()
{
	cin>>n>>V;
	for(int i=1;i<=n;i++)
	  {
	  	cin>>a>>b>>m;
	  	int j;
	  	for(j=1;m-j>=0;j<<=1)  //二进制拆分优化
	  	  {
	  	  	cnt++;
	  	  	v[cnt]=a*j;
	  	  	w[cnt]=b*j;  //存储序列三
	  	  	m-=j;
	  	  }
	  	if(m)
	  	  {
	  	  	cnt++;
	  	  	v[cnt]=a*m;
	  	  	w[cnt]=b*m;
	  	  }
	  }
	for(int i=1;i<=cnt;i++)
	  {
	  	for(int j=V;j>=w[i];j--)
	  	  {
	  	  	f[j]=max(f[j],f[j-w[i]]+v[i]);
	  	  }
	  }
	cout<<f[V];
	return 0;
}
上一篇:第三章 03 if 多重判断作用


下一篇:react源码解析18事件系统