[算法学习笔记] 多重背包--二进制拆分

多重背包

回顾一下多重背包是什么？有\(n\)种物品，每个物品都有有限个，每个物品都有重量和价值两个参数，你有一个限重为\(W\)的背包，求背包内价值最大。

我们朴素的做法是将多重背包拆分成01背包求解，因为每个物品都有有限个，假设第\(i\)个物品有\(j\)个，那么跑\(j\)次01背包即可。

但是这样复杂度会很高，由于每次将多重背包拆分成\(j\)个独立的完全背包求解。在某些题目中会超时。

如何改善呢？

状态已经优化到了极致，无法处理。我们发现算法的瓶颈在于每次暴力的将一种物品拆分成\(j\)个，跑01背包。若改善算法只能从这里入手。

二进制拆分

首先一个性质，任何一个正整数都能表示成若干个二的整次幂的和的形式，例如\(2^0,2^1,2^2,2^3\)能表示从1-7的任意整数。

那么我们每次在将一种物品拆分成\(j\)个物品的时候是不是就可以只拆分成2的整次幂！因为只拆分成二的整次幂同样也可以不重不漏的表示。

若最后拆分不成二的整次幂，直接存就好。

将每种物品的\(w\)和\(v\)拆分完后，就可以直接当作01背包跑了。
二进制拆分参考代码如下：

	int a,b,m; //分别代表v,w,cnt，其中cnt为每种物品的个数
		read(a); //快读
		read(b);
		read(m);
		int c = 1;
		while(m > c) //完全背包的二进制拆分，将完全背包拆分成01背包 
		{
			m -= c;
			w[++index] = c*b;
			v[index] = c*a;
			c*=2;
		}
		w[++index] = m*b; //若最后拆分不成，直接存
		v[index] = m*a;

典例

Luogu P1776 宝物筛选

本题实际就是一个多重背包的板子，搭配二进制拆分即可AC

Code

//二进制拆分优化完全背包典型例题。待整 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100000
#define INF 0x3f3f3f3f
using namespace std;
int n,W;
int w[N],v[N],cnt[N];
int f[N];
int maxn = -1;
template<typename type>
inline void read(type &x) //fast read 
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1)//0为空格，1为换行 fast print 
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}
int main()
{
//	freopen("input.txt","r",stdin);
	read(n);
	read(W);
	int index = 0;
	for(int i=1;i<=n;i++) 
	{
		int a,b,m;
		read(a);
		read(b);
		read(m);
		int c = 1;
		while(m > c) //完全背包的二进制拆分，将完全背包拆分成01背包 
		{
			m -= c;
			w[++index] = c*b;
			v[index] = c*a;
			c*=2;
		}
		w[++index] = m*b;
		v[index] = m*a;
	}
    for(int i=1;i<=index;i++)
    {
        for(int k = W;k>=w[i];k--)  //当01背包跑就好
		{
			f[k] = max(f[k],f[k-w[i]]+v[i]);
			maxn = max(maxn,f[k]);
		}
    }
    write(maxn,1);
	return 0;
}