倍增

倍增，或者叫二进制划分，是指将整数划分为若干个2的次幂之和，具体题型有两种。

单个整数二进制划分

参考二进制划分，整数都可以被划分为若干个2的次幂相加。（划分时每个2的次幂只用一次）

区间整数二进制划分

整数$N$可以产生一个区间$[0, N]$，将该区间内所有整数用同一2的次幂集合进行二进制划分，并且要求这些2的次幂不能生成大于$N$的整数（区间内所有整数都能用此2的次幂集合划分，并且此2的次幂集合不能划分区间外的其他整数）。(划分时每个2的次幂只用一次）

这些2的次幂应该是：$2^0$、……、$2^k$、$N-\Sigma_{i=0}^k 2^i$（其中$k$是使得$2^k\leqslant N$的最大$k$，最后一个整数不是2的次幂不过不影响划分）。

多重背包问题的倍增思想优化

问题描述详见背包问题，多重背包如果将多个相同物品都看成独立的单个物品，则转化为0/1背包问题，但是这样物品数量很多，借助倍增思想可以将物品数量减少。

对数量为si的每件原物品生成等价于$2^0$、……、$2^k$、si $-\Sigma_{i=0}^k 2^k$个原物品的新物品（$k$是满足$2^k\leqslant$ si的最大$k$），新物品能且只能组合成[0, si]内所有整数个原物品，从而用数量更少的新物品替代原物品。

// cnt统计n件每件si个的原物品全部生成等价的每件1个的新物品之后新物品的件数，初始化为0

for (int i = 1; i <= n; i++) {
    // 获得vi、wi、si
    for (int j = 1; j <= si; j *= 2) {
        si -= j;
        v[cnt] = j * vi;
        w[cnt] = j * wi;
        cnt++;
    }
    if (si > 0) {
        v[cnt] = si * vi;
        w[cnt] = si * wi;
        cnt++;
    }
}

从而，n件物品每件si个的多重背包问题转化为cnt件物品每件1个的0/1背包问题。

// 原子集合初始化：f[j] = 0 (0<=j<=m)，在前0个物品中选、体积和<=j的所有选法的最大价值可以直接得出为0

for (int i = 1; i <= cnt; i++)
    for (int j = m; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

// 最终结果：f[m]

---