多重背包问题 II

思路分析

这道题，如果套用多重背包一的思路算，要计算$4 * 10^9$，很明显是要超时间的，这时候，我们可以运用二进制合并的优化将本题转化为01背包，提高速度

1. 二进制优化：

我们之前之所以慢，就是对于每个物品取几个都得挨个枚举。我们可以通过适当打包，让我们实现能够相同的功能

对于任何一个数字$s$，我们可以把它拆分成$log s$个数字，通过这些数字可以组合出来$0$ ~ $s$中间的任意一个数字。也就是说，原来需要考虑$s$中情况，而现在只需要考虑$log s$种情况

2. 拆分方法

$s = 1 + 2 + 4 + 8 + 16 + … + 2 ^ k + c, c < 2 ^ {k + 1}$

int a;
cin >> a;
int k = 1;
while (k <= n) // 这里 c < 2 ^ (k + 1)
{
    a[++ cnt] = k; // 记录数据
    n -= k, k *= 2;
}
if (s) a[++ cnt] = s; // 最后一个大的2进制数字减完，还能有剩余，也就是c，那就单独存储 

这里$n$是拆分的数字，$a$[ ]存储拆分后的数字

3. 方法可行的证明

(1) 等价命题

我们让$c = 0$时候，$c = 2 ^ k$，可以得到下面命题。之前c的范围是$0 <= c < 2 ^ {k + 1}$
现在$c$的范围是$0 < c <= 2 ^ {k + 1}$，其实就是相当于取了次模，没有实质变化

$s = 1 + 2 + 4 + 8 + 16 + … + 2 ^ k + c, c <= 2 ^ {k + 1}$

(2) 充分性证明：

任何一个数字一定可以被拆分乘这种形式
一个数字s，用二进制表示有$n + 1$位，那么它可以拆成$n$位全是$1$的数，还有一个进位数，也就是上面的$c$(可以是$n + 1$位，此时除了第一位都是$0$)

$c = s - n$位全是1的数字
而那个$n$位全是$1$的数，把每一位用一个数字来表示，就是$1, 2, 4, 8,$ ....

(3) 必要性证明：

拆分后的数字一定能凑出来$0$ ~ $s$中的任何一个数字，$n$位二进制表示全为1的数字为x
首先对于$0$ ~ $x$，由二进制表示，我们易得，这都是可以表示的。同时加上c，那么就可以凑出来$c$ ~ $(x + c)$，也就是$c$ ~ $s$

剩下$x$ ~ $s$是需要考虑的，剩下的$x$ ~ $s$。$0$ ~ $x$的数字都可以凑出来，那么同时加上$c$， 得$c$ ~ $(n + c)$，也就是$c$ ~ $s$，都可以凑出来。已知$c$最大是比$x$大一，所以它们会是无缝衔接，也就是$0$ ~ $s$任何一个数字都可以被这样拆分后的数字组合出来

数据范围

一个物品最大空间是$2000$拆分后的物品个数是$11$，总共有一千个物品，所以最少得开一万一
我们动态规划数组优化后开的大小取决于背包大小，$2000$

时间复杂度分析

之前是对每一种情况都考虑，极限下是$O(nms)$的复杂度，现在是$O(nm log s)$，大概需要计算$2 * 10^7$可以在1s内求解了

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010; // N是拆分后物体总数， M 是背包容量

int n, m;
int v[N], w[N];
int f[M]; // 滚动数组优化后的dp数组

int main()
{
    cin >> n >> m;

    int cnt = 0; // 记录打包后的物品个数，从1开始打包
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) //一直减2的倍数
        {
            cnt ++ ;
            v[cnt] = a * k; // 打包后的体积与价值
            w[cnt] = b * k;
            s -= k; // 剩下需要打包的量
            k *= 2; // 先 * 2，下次剩余的就是与下一个比较了
        }
        if (s > 0) // 如果剩下的C存在
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt; // 打包完成

    for (int i = 1; i <= n; i ++ ) // 01背包
        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;
}