多重背包
回顾一下多重背包是什么？有\(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;
典例
本题实际就是一个多重背包的板子，搭配二进制拆分即可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;
}