背包问题

给定 $n$ 个物品，第 $i$ 个物品价值为 $c[i]$, 体积为 $w[i]$. 现有容积为 $m$ 的背包，求将物品装入背包得到的最大价值.

$f[i,v]$: 从前 $i$ 个物品中，选出总体积为 $v$ 的物品，能得到的最大价值.

• 不选第 $i$ 个物品：$f[i,v]=f[i-1,v]$.
• 选第 $i$ 个物品：$f[i,v]=f[i-1,v-w_i]+c_i$.

$$f[i,v] = \max\left\{\begin{aligned} &f[i-1,v]\\ &f[i-1,v-w_i]+c_i\quad(v≥w_i)\\ \end{aligned}\right.$$

时间复杂度：$O(nm)$.

for (int i = 1; i <= n; i ++) {
    for (int v = 0; v <= m; v ++) {
        f[i][v] = f[i - 1][v];
        if (v >= w[i])
            f[i][v] = max(f[i][v], f[i - 1][v - w[i]] + c[i]);
    }
}
// 问题的解是 f[n][m]

实际上，状态转移方程的第一维可以去掉，即让新状态覆盖旧状态，降低空间开销.

$$f[v] = \max\left\{\begin{aligned} &f[v]\\ &f[v-w_i]+c_i\quad(v≥w_i) \end{aligned}\right.$$

但在程序中，直接移除第一维会导致错误. 令 $w=1,c=2$，执行内层循环，可见错误的根源.

在内层循环中，$f[v-w]$ 不能比 $f[v]$ 先更新，否则相当于同一物品被装多次. 倒序枚举 $v$ 以解决问题.

for (int i = 1; i <= n; i ++)
    for (int v = m; v >= w[i]; v --)    // 倒序枚举
        f[v] = max(f[v], f[v - w[i]] + c[i]);

基于 01 背包，每种物品可装无限次.

$f[i,v]$: 从前 $i$ 种物品中，选出总体积为 $v$ 的物品，能得到的最大价值.

• 不选第 $i$ 种物品：$f[i,v]=f[i-1,v]$.
• 多选一个第 $i$ 种物品：$f[i,v]=f[i,v-w_i]+c_i$.

$$f[i,v] = \max\left\{\begin{aligned} &f[i-1,v]\\ &f[i,v-w_i]+c_i\quad(v≥w_i) \end{aligned}\right.$$

时间复杂度：$O(nm)$.

for (int i = 1; i <= n; i ++) {
    for (int v = 0; v < m; v ++) {
        f[i][v] = f[i - 1][v];
        if (v >= w[i])
            f[i][v] = max(f[i][v], f[i][v - w[i]] + c[i]);
    }
}

参照 01 背包 - 空间优化 中的错误做法：直接移除第一维，并升序枚举 $v$，相当于将同种物品装多次.

for (int i = 1; i <= n; i ++)
    for (int v = w[i]; v <= m; v ++)
        f[v] = max(f[v], f[v - w[i]] + c[i]);

基于 01 背包，第 $i$ 种物品可装 $s_i$ 次.

在内层循环中，分别绑定 $1,2,\cdots s_i$ 个物品作为一个物品，参与 01 背包.

$$f[v] = \max_{k=1,2,\cdots,s_i}\begin{cases} f[v]\\ f[v-k\cdot w_i]+k\cdot c_i\quad(v≥k\cdot w_i) \end{cases}$$

时间复杂度：$O(m\sum s_i)$.

for (int i = 1; i <= n; i ++)
    for (int v = m; v >= w[i]; v --)
        for (int k = 0; k <= s[i] && v >= k * w[i]; k ++)
            f[v] = max(f[v], f[v - k * w[i]] + k * c[i]);

• 任意正整数 $n$ 可拆分为 $1,2,4,\cdots,2^k,n-2^k$（$n-2^k≥0$ 且 $k$ 尽量大）.
• 相反，$1,2,4,\cdots,2^k,n-2^k$ 能且仅能组合出 $[1,n]$ 中的所有整数.

将 $s_i$ 个物品拆分为 $1,2,4,\cdots,2^k,s_i-2^k$ 个物品（共 $\log s_i$ 组），并绑定每组为一个物品，参与 01 背包. 例如，$s_i=15$ 可以拆分为以下 $4$ 组：

此 $4$ 组物品可组合出所有策略（选 $1\cdots 15$ 个物品）. 例如要选 $12$ 个物品，则同时选第 $3,4$ 组即可.

时间复杂度：$O(m\sum\log{s_i})$.

for (int i = 1; i <= n; i ++) {
    int wi, ci, s;
    cin >> wi >> ci >> s;
    for (int k = 1; k <= s; k *= 2) {
        w[++ cnt] = k * wi, c[cnt] = k * ci;
        s -= k;
    }
    if (s)
        w[++ cnt] = s * wi, c[cnt] = s * ci;
}
for (int i = 1; i <= tot; i ++)
    for (int v = m; v >= w[i]; v --)
        f[v] = max(f[v], f[v - w[i]] + c[i]);

背包体积为 $m$，有 $t$ 组物品，第 $k$ 组有 $s_k$ 个，其中第 $i$ 个体积为 $w_{ki}$，价值为 $c_{ki}$. 每组只能取走一个物品. 求将物品装入背包得到的最大价值.

$f[k,v]$：从前 $k$ 组物品中，选出总体积为 $v$ 的物品，能得到的最大价值.

• 不选第 $k$ 组：$f[k,v]=f[k-1,v]$.
• 选第 $k$ 组：$ f[k,v]=\max_{1\leq i\leq s_k}\ f[k-1,v-w_{ki}]+c_{ki}$.

$$f[k,v] = \max\left\{\begin{aligned} &f[k-1,v]\\ &\max_{1\leq i\leq s_k}\ f[k-1,v-w_{ki}]+c_{ki}\quad(v≥w_{ki}) \end{aligned}\right.$$

可以省去第一维. 时间复杂度：$O(nm)$.

for (int k = 1; k <= t; k ++)
	for (int v = m; v >= 0; v --)
		for (int i = 1; i <= s[k]; i ++)
			if (v >= w[k][i])
				f[v] = max(f[v],f[v - w[k][i]] + c[k][i]);

背包体积为 $V$，承重为 $M$. 有 $n$ 个物品，第 $i$ 个体积为 $v_i$，质量为 $m_i$，价值为 $c_i$. 求将物品装入背包得到的最大价值.

$f[p,q]$：用体积为 $p$，承重为 $q$ 的背包放物品，能获得的最大总价值.

$$f[p,q] = \max\left\{\begin{aligned} &f[p,q]\\ &f[p-v_i,q-m_i]+c_i\quad(p≥v_i,q≥m_i) \end{aligned}\right.$$

时间复杂度为 $O(nVM)$.

for (int i = 1; i <= n; i ++)
    for (int p = V; p >= v[i]; p --)
        for (int q = M; q >= m[i]; q --)
            f[p][q] = max(f[p][q], f[p - v[i]][q - m[i]] + c[i]);

基于 01 背包，求将物品放入背包的方案数.

$g[i,v]$：把前 $i$ 个物品（部分或全部）放入体积为 $v$ 的背包的方案总数.

• 不放第 $i$ 个物品：有 $g[i-1,v]$ 种
• 放第 $i$ 个物品：有 $g[i-1,v-w_i]$ 种

$$g[i,v]=g[i-1,v]+g[i-1,v-w_i]$$

同样可以省去第一维：

$$g[v]=g[v]+g[v-w_i]\quad(v≥w_i)$$

初始条件：$g[0]=1$. 因为当背包体积为 $0$ 时只有一个方案：不放任何物品.

g[0] = 1;
for (int i = 1; i <= n; i ++)
    for (int v = m; v >= w[i]; v --)
        g[v] += g[v - w[i]];

基于 01 背包，求最优方案数.

已知 01 背包 的状态转移方程：

$$f[i,v] = \max\left\{\begin{aligned} &f[i-1,v]\\ &f[i-1,v-w_i]+c_i\quad(v≥w_i)\\ \end{aligned}\right.$$

$g[i,v]$：把前 $i$ 个物品（部分或全部）放入体积为 $v$ 的背包的最优方案数.

• 若 $f[i-1,v]>f[i-1,v-w_i]+c_i$，不放物品 $i$ 最优：$g[i,v]=g[i-1,v]$.

• 若 $f[i-1,v]<f[i-1,v-w_i]+c_i$，放物品 $i$ 最优：$g[i,v]=g[i-1,v-w_i]$.

• 若相等，则两种方案都最优：$g[i,v]=g[i-1,v]+g[i-1,v-w_i]$.

for (int i = 1; i <= n; i ++) {
    for (int v = 0; v <= m; v ++) {
        f[i][v] = f[i - 1][v];
        if (v >= w[i])
            f[i][v] = max(f[i][v], f[i - 1][v - w[i]] + c[i]);
        if (f[i][v] == f[i - 1][v])
            g[i][v] += g[i - 1][v];
        if (f[i][v] == f[i - 1][v - w[i]] + c[i])
            g[i][v] += g[v - w[i]];
    }
}

省去第一维：

for (int i = 1; i <= n; i ++) {
    for (int v = m; v >= w[i]; v --) {
        int maxn = max(f[v], f[v - w[i]] + c[i]);
        int maxg = 0; // 最优方案数
        if(maxn == f[v])
            maxg += g[v];
        if(maxn == f[v - w[i]] + c[i])
            maxg += g[v - w[i]];
        f[v] = maxn, g[v] = maxg;
    }
}