多重背包-二进制优化
Ender_NaCl
·
·
个人记录
二进制分拆
对于任意一个正整数 x，一定可以分拆成这样的形式：
x = 2^0 + 2^1 + 2^2 + \cdots + 2^n + d
具体地
首先前一部分2^0 + 2^1 + 2^2 +\cdots+ 2^n可以看成是(\begin{matrix}\underbrace{111\cdots1}\\n\end{matrix})_2，为了方便，把它表示 s。为但是 x 在二进制中不一定每一位都是 1 ，所以 d 就是 x - s 的值
举一个具体的例子，比如数字 $13$，即 $(1101)_2
那么 n = 3，即s = (111)_2，所以d = (1101)_2 - (111)_2 = (110)_2 =
(6)_{10}
那么我们就可以分成 2^0,2^1,2^3,6 四份
我们可以把物品的数量进行上述拆分。
举个例子，假如一件物品重量为 v，价值为 w，数量为 13
我们可以分成四组：
重量 价值 数量
| v | w | 2^0 = 1 |
| 2v | 2w | 2^1 = 2 |
| 4v | 4w | 2^2 = 4 |
| 6v | 6w | d = 6 |
我们就把这个物品拆成上述 4 种物品存起来
对所有物品这样拆分，最后进行 0/1 背包就行了
证明正确性
有人可能会问：拆成 1,2,4,6个物品，那假如我要取3个，11个怎么办？
3 = 1 + 2
11 = 1 + 4 + 6
这两个物品个数可根据组合取到
那其他的数呢？0 ~ 13 都能通过组合取到吗？
所以我们要证明如果按上述拆分，那你一定能取遍 0 ~ x的所有数
证明如下
那么因为还有一个 $d$ ，那么就可以取 $0$ ~ $s + d$的所有数了，因为 $x = s + d$，所以就能取遍 $0$ ~ $x$ 的所有数了
证明了正确性，最后就是代码了
## 代码
```cpp
#include <iostream>
using namespace std;
int dp[201],c[50],w[50];
int main()
{
int V,N,count=0,i,j;
cin>>V>>N;
for(i = 1;i <= N;i++)
{
int C,W,co;
cin>>C>>W>>co; //依次读入空间、价值、数量
for(j = 1;j <= co;j<<=1) //寻找最大的s，j每次左移一位，依次为1，2，4…
{
c[count] = j * C; //空间乘上相应的二进制数
w[count] = j * W; //价值乘上相应的二进制数
count++;
co-=j;
}
//此时的co就是d
if(co > 0)//剩余未拆分的
{
c[count] = co * C;
w[count] = co * W;
count++;
}
}
for(i = 0;i < count;i++) for(j = V;j >= c[i];j--) dp[j] = max(dp[j],dp[j - c[i]] + w[i]); //0/1背包
cout<<dp[V];
return 0;
}
```