目录

• 零. dp 分析
• 一. 分析
• 二. 二进制优化
• 三. 代码

零. dp 分析

• 状态表示
  • 集合：所有…的集合
    • 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
  • 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
• 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。

一. 分析

• 01背包中：f[i][j] 可以划分为第 i 个物品选还是不选，分别对应之前的两个状态，从而可以转台转移和计算
• 完全背包：假设容积 j 可以容纳至多 k 个第 i 个物品，那么f[i][j]可以划分为第 i 个物品拿 $[0, k]$ 个，总计 $k + 1$ 个状态，即下方所示。因此理所当然的可以想到对 f[i][j] 的计算应循环 $k + 1$ 次，那么就是三重循环，当 container = 1000, vol[i] = 1 时，时间复杂度可以达到 $O(10^{9})$ 超时，因此优化状态转移，即 f[i][j] = max(f[i-1][j], f[i][j-vol[i]] + val[i]) 。
• 多重背包Ⅰ：容积 j 可以容纳至多 k 个第 i 个物品，第 i 个物品总共 num[i] 个，综合这两个限制，假设第 i 个物品最多拿 x = min(k, num[i]) 个。那么f[i][j]可以划分为第 i 个物品拿 $[0, x]$ 个，总计 $x + 1$ 个状态。区别于完全背包，多重背包中，状态 f[i][j] 和状态 f[i][j-vol[i]] 之间联系更加复杂，即 f[i][j] 和 f[i][j-vol[i]] 可能选用不同的数量来分别得到其最大值，因此之前的优化状态转移不再适用，即要使用完全背包的朴素解法。注意：
  • f[i][j] 拿了 x 个第 i 个物品（x 为上述假设的最大数量）， f[i][j+1] 仍有可能拿 x 个第 i 个物品.
  • f[i][...] 含义：要计算拿几个第 i 个物品，可以使从相应的 f[i-1][...-(几个*vol[i])] 状态转移过来后，可以取得最大值。即， f[i][...] 都是从对应方案的 f[i-1][...] 转移过来的
  • f[i][j] 和 f[i][j-vol[i]] 可能选用不同的数量来分别得到其最大值，因此不能用 f[i][j] = max(f[i-1][j], f[i][j-vol[i]] + val[i]) 来计算 f[i][j]
• 多重背包Ⅱ：题目主要考察多重背包的二进制优化。数据范围增大，朴素的三重循环解决多重背包的方法一定会超时，因此要寻求优化。在上一篇多重背包的题解中，已经分析了通过状态转移优化计算已经不可能。因为可能选取完全不同的方案（我之前的理解不够彻底）。前提同上：容积 j 可以容纳至多 k 个第 i 个物品，第 i 个物品总共 num[i] 个，综合这两个限制，假设第 i 个物品最多拿 x = min(k, num[i]) 个。那么f[i][j]可以划分为第 i 个物品拿 $[0, x]$ 个，总计 $x + 1$ 个状态。在容积 j 足够的前提下，写出 f[i][j] 和 f[i][j-vol[i]] 的状态转移。

f[i][j] = max(f[i-1][j-0*vol[i]] + 0*val[i],   // 1：  拿 0 个第 i 个物品
              f[i-1][j-1*vol[i]] + 1*val[i],   // 2：  拿 1 个第 i 个物品
              f[i-1][j-2*vol[i]] + 2*val[i],   // 3：  拿 2 个第 i 个物品
              ...,                             // ...
              f[i-1][j-x*vol[i]] + x*val[i],   // x+1：拿 x 个第 i 个物品

f[i][j-vol[i]] = max(f[i-1][j-1*vol[i]] + 0*val[i],         // 1：  拿 0 个第 i 个物品
                     f[i-1][j-2*vol[i]] + 1*val[i],         // 2：  拿 1 个第 i 个物品
                     f[i-1][j-3*vol[i]] + 2*val[i],         // 3：  拿 2 个第 i 个物品
                     ...,                                   // ...
                     f[i-1][j-(x+1)*vol[i]] + x*val[i],     // x+1：拿 x 个第 i 个物品

区别于完全背包的状态转移，这里的 x < k 且当 j 足够大时，就会导致 f[i][j-vol[i]] 的状态转移中的最后一项不在 f[i][j] 的状态转移范围之内。而我们求出 f[i][j-vol[i]] 之后，没有办法求去除最后一项的 max 值（或者很难），因此导致无法通过优化状态转移来计算。

二. 二进制优化

从多重背包Ⅰ朴素解法入手谋求优化。

朴素解法中我们要对每个 f[i][j] 遍历其状态转移方程中的各个状态来计算。总共三个循环：

• 前 i 个物品
• 容积为 j
• 选取 k 个第 i 个物品

二进制优化的思路：对于第 i 个物品，“打包”成若干组，使得每个若干组选与不选就可以表示第 i 个物品所有可能的选取状态。例：第 i 个物品总共 1023 个，分成 “1、2、4、8、16、32、64、128、256、512”这几个组，每个组选与不选组合起来就可以表示第 i 个物品选择 $[0, 1023]$ 个的所有状态。

• 打包的方法：对于个数不等于 $2^n - 1$ 的，如何划分： $sum = 2^n=$ 其中 $n$ 从 0 开始取，每取一个 $n$ 得到一个对应的打包，即 $sum$ 个第 i 个物品，当剩余的第 i 个物品的数量小于 $sum$ 时，取其剩余的数量作为第 i 个物品最后一个打包。
• 举例验证其可以表示选取第 i 个物品所有可能数量：假设 200 个，分别打包为表示数量 “1、2、4、8、16、32、64、73” 的 8 个物品，前 7 个物品可以表示选取 $[0, 127]$ 个第 i 个物品，当选取第 8 个物品时，结合前 7 个物品，可以表示选取 $[73+0, 73+127]$ 第 i 个物品，即 $[73, 200]$。虽然有重复区间但可以表示所有可能。
• 经过二进制优化，多重背包问题（第 i 个物品有限个）就转化为了01背包问题（每个物品选还是不选）。物品总数量约为 $n \times log_{2} (max(num[i])) \approx 1.2 \times 10^{4} \quad (n=1000, max(num[i])\approx2000)$。由 AcWing 2. 01背包 可知，总的时间复杂度约为 $O(10^7)$，计算机一秒可以执行的操作约为 $O(10^8)$ （一亿）。因此不超时。

三. 代码

难点主要在于实现打包物品，转化问题为 01 背包问题。$k = 2^n$，$num$ 为当前第 i 个物品的剩余数量，$n$ 从 0 开始取。当 $num$ 恰为或者大于当前 $2^n$ 时直接打包，否则把剩余的物品直接打包。

• 打包时注意要重新计算打包起来的物品的体积和价值。
• 打包好之后就是一个简单的 01 背包问题。

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1.2e4 + 5;

int val[N], vol[N];
int f[N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int number = 0, container = 0, cnt = 0;
    cin >> number >> container;
    _rep_le(i, 1, number) {
        int va = 0, vo = 0, num = 0;
        cin >> vo >> va >> num;

        int k = 1;
        while(k <= num) {
            cnt ++;
            val[cnt] = va * k;
            vol[cnt] = vo * k;

            num -= k;
            k *= 2;
        }
        if(num > 0) {
            cnt ++;
            val[cnt] = va * num;
            vol[cnt] = vo * num;
        }
    }

    _rep_le(i, 1, cnt) {
        // first i items
        _rep_ge(j, vol[i], container) {
            f[j] = max(f[j - vol[i]] + val[i], f[j]);
        }
    }

    cout << f[container] << endl;

    return 0;
}