前言

一开始看了3次视频还是一头雾水，看了前面大佬们的题解也还是一脸懵逼，最后十分感谢一篇 博客 的讲解出多重背包的二进制优化的三个要点，最后去看视频。
我才完全解决我最重要的疑惑：二进制优化，它为什么正确，为什么合理，凭什么可以这样分？？

题目

完全背包的二进制优化

样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

数据范围

0 < N ≤ 1000
0 < V ≤ 2000
0 < vi,wi,si ≤ 2000

疑惑1：为什么最后一项会是$f[i-1,j-(S+1)v]+Sw$??

在完全背包中,通过两个状态转移方程：

$f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w, .....)$
$f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w, f[i-1,j-2v]+2w , .....)$
通过上述比较，可以得到 $f[ i ][ j ] = max(f[ i - 1 ][ j ],f[ i ][ j - v ] + w)$。

再来看下多重背包,

$f[i , j ]$ = $max( f[i-1,j] ,f[i-1,j-v]+w ,f[i-1,j-2v]+2w ,..... f[i-1,j-Sv]+Sw, )$
$f[i , j-v]$= $max( f[i-1,j-v] ,f[i-1,j-2v]+w, ..... f[i-1,j-Sv]+(S-1)w$,$f[i-1,j-(S+1)v]+Sw)$

怎么比完全背包方程比较就多出了一项?

其实，一般从实际含义出发来考虑即可，这里是在分析$f[i,j-w]$这个状态的表达式，首先这个状态的含义是 从前i个物品中选，且总体积不超过j-w的最大价值， 我们现在最多只能选s个物品，因此如果我们选s个第i个物品，那么体积上就要减去 $s * v$,价值上就要加上$s * w$，那更新到状态中去就是 $f[i - 1, j - v - s * v] + s * w $

那为什么完全背包不会有最后一项？

完全背包由于对每种物品没有选择个数的限制，所以只要体积够用就可以一直选，没有最后一项。

疑惑2：为什么不能用像完全背包一样去优化？

y总算法基础课视频 4分10秒-5分42秒

疑惑3：二进制优化，它为什么正确，为什么合理，凭什么可以这样分？？

我们首先确认三点：

（1）我们知道转化成01背包的基本思路就是：判断每件物品我是取了你好呢还是不取你好。

（2）我们知道任意一个实数可以由二进制数来表示，也就是$2^0~2^k$其中一项或几项的和。

（3）这里多重背包问的就是每件物品取多少件可以获得最大价值。

分析：

• 如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。那么根据数据范围，这样的时间复杂度是$O(n^3)$,也就是$10^9$，这样是毫无疑问是会TLE的。

• 假如10个取7个好，那么在实际的遍历过程中在第7个以后经过状态转移方程其实已经是选择“不取”好了。现在，用二进制思想将其分堆，分成$k+1$个分别有$2^k$个的堆，然后拿这一堆一堆去问，我是取了好呢，还是不取好呢，经过dp选择之后，结果和拿一个一个来问的结果是完全一样的，因为dp选择的是最优结果，而根据第二点任意一个实数都可以用二进制来表示，如果最终选出来10个取7个是最优的在分堆的选择过程中分成了$2^0=1,2^1=2,2^2=4,10 - 7 = 3$ 这四堆，然后去问四次，也就是拿去走dp状态转移方程，走的结果是第一堆1个，取了比不取好，第二堆2个，取了比不取好，第三堆四个，取了比不取好，第四堆8个，取了还不如不取，最后依旧是取了$1+2+4=7$个。

Tip:参考博客

如果仍然不是很能理解的话，取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次

二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照$1,2,4,8,16,.....512$分到10个箱子里，那么由于任何一个数字$x \in [0,1023]$ (第11个箱子才能取到1024，评论区有讨论这个)都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 $≤10次$ 。

比如：
- 如果要拿$1001$次苹果，传统就是要拿$1001$次；二进制的思维，就是拿7个箱子就行（分别是装有$512、256、128、64、32、8、1$个苹果的这7个箱子）,这样一来，1001次操作就变成7次操作就行了。

这样利用二进制优化，时间复杂度就从 $O(n^3)$ 降到$O(n^2logS)$,从$4*10^9$降到了$2*10^7$。

代码

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    for(int i = 1;i <= n ;i ++)
        for(int j = m ;j >= v[i];j --)
            f[j] = max(f[j],f[j-v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

后言

把自己菜哭了。。。。