背包问题的简单总结

本文最简短地总结一下经典的背包问题。

只总结 01 背包完全背包多重背包分组背包,不含优化。

参考书:《算法竞赛进阶指南》· 李煜东

背包问题的四种模型的代码有一定的规律,这也是本文要总结它的原因。

四种背包模型,都是 背包容积有限、最大化总价值,不同点在于物品的分布和选择方式。

以下的四种模型,$f(j)$ 均定义为背包放入总体积为 $j$ 的物品时的最大价值。

01 背包

给定 $n$ 个物品,其中第 $i$ 个物品的体积为 $v_i$,价值为 $w_i$。有一个容积为 $m$ 的背包。要求选择一些物品放入背包, 使得物品总体积不超过 $m$ 的情况下,物品的总价值最高。

关键点:每个物品只可使用一次

不断加入每一个物品 $i$,对于每一个总体积 $j$ 有两种情况:

  1. 不选第 $i$ 个物品,此时取值不变,仍为 $f(j)$。
  2. 选择第 $i$ 个物品,此时除去当前物品的体积后,即 $j-v_i$ 体积限制下的最大价值、再加上第 $i$ 个物品的价值 $w_i$。

所以推导方程是:

\[f(j) = \max_{v_i \leq j \leq m} { \{ f(j), f(j-v_i) + w_i \} }\]

代码实现如下:

int f[MAX_M];
memset(f, 0xcf, sizeof f); f[0] = 0;

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]);
}
int ans = 0;
for (int j = 0; j <= m; j++) ans = max(ans, f[j]);

注意,其中标记部分使用了 倒序循环

下图中:

  1. 左边是没有考虑加入当前物品的 $i-1$ 阶段
  2. 右边是已进入「加入了第 $i$ 个物品」的 $i$ 阶段

倒序遍历的时候,$f$ 数组上的 dp 过程就是从 $i-1$ 到 $i$ 阶段进行转移。

由于计算 $f(j)$ 时,左边的 $f(j-v_i)$ 仍处于 $i-1$ 阶段,所以对每个 $f(j)$ 来说,第 $i$ 个物品仅考虑了一次。

完全背包

给定 $n$ 种物品,其中第 $i$ 种物品的体积为 $v_i$,价值为 $w_i$,并且每种物品有无数个。有一个容积为 $m$ 的背包。 要求选择若干种物品放入背包,使得物品总体积不超过 $m$ 的情况下,物品的总价值最高。

关键点:每种物品可使用无限次

和 01 背包的 dp 方程也一样,但是不同之处在于:内层循环正序

int f[MAX_M];
memset(f, 0xcf, sizeof f); f[0] = 0;

for (int i = 1; i <= n; i++) {       // 物品
    for (int j = v[i]; j <= m; j++)  // 体积
        f[j] = max(f[j], f[j - v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; j++) ans = max(ans, f[j]);

类似于 01 背包的分析,从左向右正序遍历时,$f$ 数组上的 dp 过程就是从 $i-1$ 到 $i$ 阶段进行转移。

由于计算 $f(j)$ 时,左边的 $f(j-v_i)$ 已经处于 $i$ 阶段,所以对每个 $f(j)$ 来说,第 $i$ 种物品会被考虑多次。 而且,每种物品被被考虑使用多少次,是不加限制的。所以说,完全背包问题也叫做「无限制的背包问题」(Unbounded knapsack)。

多重背包

给定 $n$ 种物品,其中第 $i$ 种物品的体积为 $v_i$,价值为 $w_i$,并且有 $c_i$ 个。有一个容积为 $m$ 的背包。要求选择一些物品放入背包, 使得物品总体积不超过 $m$ 的情况下,物品的总价值最高。

关键点:每种物品只可使用给定次数

多重背包,就是 01 背包基础上,每种物品重复了多次。

可直接把多重背包看成共有 $\sum^n_{i=1}{c_i}$ 个物品的 01 背包问题。

dp 定义和 01 背包是一样的。

下面代码中,高亮的两行即相当于 01 背包中的外层循环

int f[MAX_M];
memset(f, 0xcf, sizeof f); f[0] = 0;
for (int i = 1; i <= n; i++) {           // 物品种数
    for (int k = 1; k <= c[i]; k++)      // 每种物品的个数
        for (int j = m; j >= v[i]; j--)  // 体积
            f[j] = max(f[j], f[j - v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; j++) ans = max(ans, f[j]);

这种方法时间复杂度较高,常用的优化手段是 二进制拆分 和 单调队列优化 $O(nm)$,本文暂不包含多重背包的优化内容。

分组背包

给定 $n$ 组物品,其中第 $i$ 组有 $c_i$ 个物品。第 $i$ 组的第 $k$ 个物品的体积为 $v_{ik}$,价值为 $w_{ik}$。 有一个容积为 $m$ 的背包。要求选择一些物品放入背包,每组至多选择一个物品,使得物品总体积不超过 $m$ 的情况下,物品的总价值最高。

关键点:每组至多选择一个物品

考虑加入第 $i$ 组,对于每一个总体积 $j$ 有两种情况:

  1. 不选第 $i$ 组的物品,此时取值不变,仍为 $f(j)$。
  2. 选择第 $i$ 组的某个物品 $k$,此时除去此物品的体积后,即 $j-v_{ik}$ 体积限制下的最大价值、再加上当前选择物品的价值 $w_{ik}$。

推导方程如下,和 01 背包几乎一样:

\[f(j) = \max \begin{cases} f(j) &\\ \max_{1 \leq k \leq c_i} { \{ f(j-v_{ik}) + w_{ik} \}} &\end{cases}\]

代码实现如下:

int f[MAX_M];
memset(f, 0xcf, sizeof f); f[0] = 0;
for (int i = 1; i <= n; i++) {    // 物品
    for (int j = m; j >= 0; j--)  // 体积
        for (int k = 1; k <= c[i]; k++)
            if (j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
int ans = 0;
for (int j = 0; j <= m; j++) ans = max(ans, f[j]);

相当于,内层循环在每个组里面选一个最优的代表元素

对于每个目标体积 $j$,相当于对于组内每个物品 $v_{ik}$ 都倒序地推导一次 $f(j)$,这样 $f(j)$ 才可以取得整个第 $i$ 个小组加入后的总的最值。

对 $k$ 的循环必须放在内层,也就是说第 $i$ 组物品的枚举整体在 $j$ 的倒序循环之内,这样才可以保证整个组内最多挑选一个物品。

下图中,左侧黄色部分仍处于 $i-1$ 阶段,右侧绿色已经处于 $i$ 阶段,$k$ 的循环自上而下进行,转移总是从黄色区域(没考虑 $i$ 物品时)到绿色区域, 先自上向下、再自右向左,才确保每一组物品中最多使用一个。 如果把 $k$ 的循环放在 $j$ 循环的外面,就会存在绿色区域向黄色区域的转移了,打破了这一限制。

简而言之,分组背包是在 01 背包的基础上对每个目标体积对组内物品依次执行取最值。

一些题目

数字组合

给定 $N$ 个正整数 $A_1$, $A_2$, …, $A_N$, 从中选出若干个数,使它们的和为 $M$,求有多少种选择方案。

-- 来自 《算法竞赛进阶指南》acwing 278

每个元素只可利用一次,属于 01 背包问题,只是取最值变成了求和。

定义 $f(j)$ 表示凑出来和为 $j$ 的时候的方案数。

要凑出来 $j$,就要考虑每个 $j-a_i$ 的方案数,然后求和。

\[f(j) = \sum_{a_i \leq j \leq m} { f(j-a_i) }\]

最开始,$f(0)$ 的方案数钦定为 $1$,只是为了递推式的合法性,你可以代入 $i=1$ 的情况,来分析 $i=0$ 的情况 $f$ 的合理取值。

数字组合 - C++ 代码
const int N = 110;
const int M = 10010;

int n, m;

int a[N];
int f[M];

int solve() {
    memset(f, 0, sizeof f);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--)
            f[j] += f[j - a[i]];
    return f[m];
}
自然数拆分

给定一个自然数 $N$,要求把 $N$ 拆分成若干个正整数相加的形式,参与加法运算的数可以重复。

-- 来自 《算法竞赛进阶指南》acwing 279

每个参与计算的自然数可以重复使用,是完全背包问题。

此时每个自然数 $i$ 的体积就是 $i$ 本身,总体积限制就是 $n$。

推导的方程式和 数字组合 问题是类似的:

\[f(j) = \sum_{i \leq j \leq n} { f(j-i) }\]

只需要把内层变为正序循环:

自然数拆分 - C++ 代码
using ull = unsigned long long;
const ull mod = 2147483648;

int solve(int n) {
    ull f[n + 1];
    memset(f, 0, sizeof f);

    f[0] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = i; j <= n; j++) {
            f[j] += f[j - i] % mod;
        }
    }
    return f[n] % mod;
}
砝码称重

有 1g、2g、3g、5g、10g、20g 的 6 种砝码,其中第 $i$ 种砝码有 $a_i$ 种。 总重量不超过 1000g。可以表示成多少种重量?

-- 来自 洛谷 P2347 砝码称重

总重量限制 $M=1000$,每种物品有 $a_i$ 个,定义 $f(j)$ 表示拼成总重量为 $j$ 的方案数,最后统计 $f$ 非 $0$ 的 $j$ 的个数即可,属于多重背包问题,套入模型即可。

前面已说过,朴素的多重背包就相当于把「每种物品重复的多次」展开后的 01 背包问题。

砝码称重 - C++ 代码
const int M = 1000;
int a[7]; // 第 i 种物品有 a[i] 个
int v[7] = {0, 1, 2, 3, 5, 10, 20}; // 每种物品的重量,即模型中的「体积」
int f[M + 1]; // f[j] 表示拼成重量 j 的方案数

int solve() {
    memset(f, 0, sizeof f);

    f[0] = 1;
    for (int i = 1; i <= 6; i++)
        for (int k = 1; k <= a[i]; k++)
            for (int j = M; j >= v[i]; j--)
                f[j] += f[j - v[i]];

    int ans = 0;
    for (int j = 1; j <= M; j++) if(f[j]) ans ++;
    return ans;
}
分割等和子集

给你一个只包含正整数的非空数组。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

-- 来自 leetcode 416

这个问题和 数字组合 十分相似,属于 01 背包问题。

定义 $f(j)$ 表示凑出来和为 $j$ 的方案是否可行,方程式如下:

\[f(j) = \forall_{a_i \leq j \leq m} { \{ f(j) \lor f(j-a_i) \} }\]

代码实现如下,同样注意钦定初始 $f(0)$ 是 $true$:

分割等和子集 - C++ 代码
class Solution {
   public:
    bool canPartition(vector<int>& a) {
        int n = a.size();
        int sum = accumulate(a.begin(), a.end(), 0);
        if (sum & 1) return false;  // 奇数不行

        int m = sum / 2;
        bool f[m + 1];
        memset(f, 0, sizeof f);
        f[0] = true;

        for (int i = 1; i < n; i++) {
            for (int j = m; j >= a[i]; j--)
                f[j] |= f[j - a[i]];
        }
        return f[m];
    }
};
目标和

给你一个非负整数数组 a 和一个整数 target

向数组中的每个整数前添加 +- ,然后串联起所有整数,可以构造一个表达式:

例如,nums = [2, 1] ,可以在 2 之前添加 + ,在 1 之前添加 -,然后串联起来得到表达式 +2-1

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

-- 来自 leetcode 494. 目标和

比如说,a=[1,1,1,1,1]target=3 的情况,共有 5 种方案:

-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

这个题目挺巧妙的,关键点在于识破问题的转化玄机。

如果全部填入 + 号,那么计算结果就是总和 sum

+1 + 1 + 1 + 1 + 1 = 5

那么,把其中一部分加号,变成 - 号,来凑 tagert,比如下面就是一种方案:


+1 + 1 + 1 + 1 + 1 = 5
// =>
+1 + 1 + 1 + 1 - 1 = 3

加号变减号,其实是减去了两倍的数值,假设总共要减去两倍的 m 的数值才可以凑成:

sum - 2*m = target

问题可以转化为:

从原数组中挑选一部分数字,应用上减号,使得总体减去的结果是 m=(sum-target)/2

如此,即转化成计算拼成和为 m 的 01 背包问题,其他不必赘述。

目标和 - C++ 代码
class Solution {
   public:
    int findTargetSumWays(vector<int>& a, int target) {
        int sum = accumulate(a.begin(), a.end(), 0);
        int m = (sum - target);
        if (m & 1 || m < 0) return 0; // 非法情况,拼不成
        m >>= 1;  // 除以 2
        int n = a.size();
        // 01 背包
        int f[2001];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = m; j >= a[i]; j--)
                f[j] += f[j - a[i]];
        return f[m];
    }
};
最大约数和

选取和不超过 $S$ 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。

-- 来自 洛谷 P1734

例如,$S=11$ 时,取 $4$ 和 $6$,结果是:

(1 + 2) + (1 + 2 + 3) = 9 // 注意 1 的约数是自己,不符合要求,所以不含在内

对于每个不超过 $S$ 的整数 $i$,定义其价值为它所有的约数之和 $w_i$,即可转化为 01 背包问题。

比如 $4$ 的价值是 $1+2=3$,再比如 $6$ 的价值是 $1+2+3=6$。但是注意 $1$ 的价值是 $0$。

求每个整数的价值 $w_i$ 时,只需遍历到 $\sqrt{i}$ 即可,细节是,注意排除自身。

最大约数和 - 预处理价值数组 - C++ 代码
const int N = 1000 + 1;
int w[N];  // 价值数组

memset(w, 0, sizeof w);

for (int i = 1; i <= S; i++) {
    if (i > 1) w[i] += 1; // i > 1 时,约数至少包含 1
    // 2~sqrt(i) 范围内的约数 j 和 i/j
    int j = 2;
    for (; j * j < i; j++)
        if (i % j == 0) w[i] += j + i / j;
    // 完全平方数时注意防止重复,sqrt(i)
    if (j * j == i) w[i] += j;
}

以 $S$ 作为体积限制,物品 $i$ 的体积是 $i$,价值是 $w_i$,求最大价值。因为要求取不同的若干个数,所以是 01 背包模型,直接套入求解即可。

最大约数和 - 01 背包 - C++ 代码
int f[N];  // 01 背包 dp 数组
memset(f, 0xcf, sizeof f); f[0] = 0;

for (int i = 1; i <= S; i++) {
    for (int j = S; j >= i; j--)
        f[j] = max(f[j], f[j - i] + w[i]);
}

int ans = 0; // 答案是 f 的最大值
for (int j = 0; j <= S; j++) ans = max(ans, f[j]);
return ans;
完全平方数

输入一个不超过 $10000$ 的正整数 $m$,求它可以表示成最少几个平方数的和(不包括 $0$)。

比如 $m=12$ 时的答案是 $3$,表示方式是 $4+4+4$。

-- 来自 leetcode 279. 完全平方数

洛谷上有一个类似的题目: 洛谷 1679 神奇的四次方数

把每个完全平方数看做背包体积,预处理出来物品的体积数组:

完全平方数 - 预处理体积数组 C++ 代码
const int K = 100 + 5;
int v[K];  // 体积数组

// 预处理体积数组, 最多到 k=sqrt(m)
int k = 1;
while (1) {
    int s = k * k;
    if (s > m) break;
    v[k++] = s;
}

背包的总体积限制是 $m$,定义 $f(j)$ 表示拼成 $j$ 的最少的平方数的个数。

那么转移方程仍然是,依次考虑每个数字 $i$,选或者不选它:

\[f(j) = \min { \{ f(j), f(j-v_i) + 1 \}}\]

由于目标是取最小值,所以初始化 $f(j)$ 数组到无穷大。

最初的情况,$f(0) = 0$。

每个数字的使用次数不加限制,代入完全背包模型即可,$f(m)$ 即是答案。

完全平方数 - C++ 代码
const int K = 100 + 5;
const int M = 10000 + 5;
int f[M];
int v[K];  // 体积数组

class Solution {
   public:
    int numSquares(int m) {
        // 预处理体积数组, 最多到 sqrt(m)
        int k = 1;
        while (1) {
            int s = k * k;
            if (s > m) break;
            v[k++] = s;
        }

        // 代入完全背包
        memset(f, 0x3f, sizeof f);
        f[0] = 0;

        for (int i = 1; i < k; i++) {
            for (int j = v[i]; j <= m; j++) {
                f[j] = min(f[j], f[j - v[i]] + 1);
            }
        }
        return f[m];
    }
};
数组的均值分割

将整数数组 a 分割为两个非空子数组,使得各自的平均值相等。

如果可以如此分割,则返回 true,否则返回 false

a 的元素大小范围在 [0, 10^4] 内,元素个数不超过 30 个。

-- 来自 leetcode 805. 数组的均值分割

比如说,a[1,2,3,4,5,6,7,8] 的时候,可以分割为:[1,4,5,8][2,3,6,7]

首先,数组大小 n1 的时候肯定是不行的,特判排除。

假设分割后的两个子数组的平均数是 t(它可能是个小数), 并假设其中一个数组的大小是 k,整个数组的和是 s,那么有:

t * k + t * (n-k) = s
// =>
t = s/n

也就是说,这个平均值一定是整个数组的平均值

但是,每个数组的和不一定是 s/2,个数也不一定相等,比如 [5,3,11,19,2]

不过,其中肯定有一个子数组的和是不大于 s/2

这和 分割等和子集 问题非常相似,只是要求更严格一点,可以基于 01 背包来考虑。

定义 $f(j, k)$ 表示使用 $k$ 个元素拼成和为 $j$ 是否可行的布尔值。

这里,相对于原本的 01 背包模型,新加入一个维度 $k$ 以方便计算平均数来验证答案。

不断放入 $a_i$,对于和为 $j$ 的推导,需要考虑每一个可能的 $k$:

  • 不选 $a_i$ 时,$f(j, k)$ 不变。
  • 选择 $a_i$ 时,剔除 $a_i$ 元素后、应该考虑 $f(j-a_i, k-1)$ 是否可行。

不过,目前 $f$ 只描述了拼成目标和是否可行,要进一步验证平均数是否为 $s/n$。

初版代码实现如下:

数组的均值分割 - 优化前 - C++ 代码
const int M = (1e4 * 30) / 2 + 1;
class Solution {
   public:
    bool splitArraySameAverage(vector<int>& a) {
        int n = a.size();
        int s = accumulate(a.begin(), a.end(), 0);
        if (n == 1) return false;
        // 肯定有一个子数组和不大于 s/2, 足够
        int m = s / 2;
        // 拼成和 m 且花费 k 个数字是否可行
        bool f[M][30];
        memset(f, 0, sizeof f); f[0][0] = true;

        for (int i = 0; i < n; i++) {
            for (int j = m; j >= a[i]; j--)
                for (int k = 1; k <= n - 1; k++) {
                    f[j][k] |= f[j - a[i]][k - 1];
                    // 验证 j/k == s/n
                    if (f[j][k] && (j * n == s * k))
                        return true;
                }
        }
        return false;
    }
};

这个实现可以勉强 AC,考虑到 $k$ 的取值范围肯定不大于 30,可以考虑二进制优化。

定义 $f(j)$ 为一个整数,其低位起第 $k$ 个比特是 $1$ 表示拼成和为 $j$ 且花费 $k$ 个数字是可行的。

如此一来,原本最内层的循环可以简化,就是说 $k$ 从 $1…n-1$ 的 dp 转移过程,可以简化成一个语句:

f[j] |= f[j - a[i]] << 1;

验证环节则可以通过依次检查每个 $j$ 的每一个比特来进行。

最终优化后的代码实现如下:

数组的均值分割 - 优化后 - C++ 代码
const int M = (1e4 * 30) / 2 + 1;
class Solution {
   public:
    bool splitArraySameAverage(vector<int>& a) {
        int n = a.size();
        int s = accumulate(a.begin(), a.end(), 0);
        if (n == 1) return false;
        // 肯定有一个子数组和不大于 s/2, 足够
        int m = s / 2;
        // f[j] 的第 k 位 bit 是 1 表示拼成和 m 且花费 k 个数字可行
        int f[M];
        memset(f, 0, sizeof f); f[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = m; j >= a[i]; j--)
                f[j] |= f[j - a[i]] << 1;
        //  验证
        for (int j = 0; j <= m; j++) {
            for (int k = 1; k <= n - 1; k++) {
                if ((f[j] & 1 << k) && (j * n == s * k))
                    return true;
            }
        }
        return false;
    }
};
组合总和

给你一个由 不同 整数组成的数组 a,和一个目标整数 m。请你从 a 中找出并返回总和为 m 的元素组合的个数。

-- 来自 leetcode 377. 组合总和 Ⅳ

例如:a[1,2,3]m4 时有 7 种可行组合:

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

这个问题非常具有迷惑性,注意所谓的「组合」,其实根本不是组合,而是「排列」。比如说 (1,2,1)(2,1,1) 算作两种可行方案。

所以这不算一个背包问题,拿完全背包模型去做是错误的,会少算。

这个问题类似经典的 爬楼梯问题 (是不是没想到)。

定义 $f(j)$ 为总和为 $j$ 的时候的方案总数。

要想获得 $j$,就要考虑从前面的 $f$ 转移而来,转移的方式,就是考虑 每个数字 $a_i$ 作为转移路径:

\[f(j) = \sum_{0 \leq i \leq n} { f(j-a_i) }\]

这好比说,要爬到 $j$ 层楼梯,可行的爬楼梯步数从数组 $a$ 中获取,一共有多少种方案。

代码实现如下:

const int N = 201;
const int M = 1001;
unsigned int f[M];

memset(f, 0, sizeof f);
f[0] = 1;
for (int j = 0; j <= m; j++)
    for (int i = 0; i < a.size(); i++)
        if (j >= a[i]) f[j] += f[j - a[i]];
return f[m];

这看起来和完全背包问题很像,但是不同点在于:每次计算一个 $f(j)$ 都要考虑全部的数字 $a_i$。 而完全背包模型只能考虑当前阶段 $i$ 之前的物品。

下面的图可以清晰地看到二者的差别,其中绿色区域是可行的转移来源:

  • 左边的是当前的问题,转移路径可以来自全部物品,不同的路径也会有相同的 dp 值,所以适合当前的「排列」计数问题。
  • 右边的是完全背包问题,因为每次转移都只能从左下方而来,所以转移路径是「上坡线」,只会有一条,也就是与排列无关。

从动态规划的角度来看,二者的 阶段划分 和 转移方式 不同:

  1. 完全背包问题,是以物品 $a_i$ 来划分阶段,再考虑每个体积 $j$ 的转移。
  2. 这个爬楼梯问题,是以目标 $j$ 来划分阶段,使用每个 $a_i$ 来转移。

从代码上来看,区别仅在于 内外层循环的对象不同: 求排列数的时候外层循环目标体积、内层循环物品。背包问题则反之。

硬币

给定 $N$ 种硬币,其中第 $i$ 种硬币的面值为 $A_i$,共有 $C_i$ 个。 从中选出若干个硬币,把面值相加,若结果为 $S$ ,则称 “面值 $S$ 能被拼成”。 求 $1∼M$ 之间能被拼成的面值有多少个。

-- 来自 《算法竞赛进阶指南》acwing 281

一眼多重背包,此外和 分割等和子集 问题类似,是判定性问题。

前面说过,多重背包的外两层循环可以看成 01 背包的外层循环。

定义 $f(j)$ 为是否可以拼成面值为 $j$ 的布尔值,则 dp 方程为:

\[f(j) = \forall_{1 \leq k \leq c_i} \forall_{a_i \leq j \leq m} { \{ f(j) \lor f(j-a_i) \} }\]

代码实现如下:

硬币 - C++ 代码
const int N = 101;
const int M = 1e5 + 10;
const int C = 1001;

int n, m;
int a[N], c[N];
bool f[M];

int solve() {
    memset(f, 0, sizeof f);
    f[0] = true;
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= c[i]; k++)
            for (int j = m; j >= a[i]; j--)
                f[j] |= f[j - a[i]];
    int ans = 0;
    for (int i = 1; i <= m; i++) ans += f[i];
    return ans;
}

这样可以通过测试用例的正确性,但是会超时,复杂度太高。

注意到,当前问题是一个「可行性」问题,而不是最优化问题。

因为只关心 $f(j)$ 是否为 $true$,其实不必每个阶段把 $c_i$ 个硬币都循环一次。

首先,如果在放入第 $i$ 种硬币时,$f(j)$ 已经是 $true$,那么没必要再考虑它了。

接下来 $f(j)$ 只有可能由 $f(j-a_i) = true$ 的情况转移而来。

如果转换一下思路,不直接基于多重背包模型,而是基于完全背包模型。

更严格地说,是 「使用次数受限制的」完全背包模型

for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++)  // 注意是正序
        if (!f[j] && f[j-a[i]] && check(j))
            f[j] = 1;
}

其中的 check 函数用以限制第 $i$ 种硬币的使用次数不得超过 $c_i$。

假设一个数组 $used(j)$ 表示在考虑放入第 $i$ 种硬币时、要拼成面值 $j$ 所需的硬币 $i$ 的最少个数。

如果面值 $j-a_i$ 可以拼成,只需再使用一次硬币 $i$,那么面值 $j$ 也可以拼成,所以 $used$ 数组的递推关系式如下:

\[used(j) = used(j-a_i) + 1\]

那么 check 函数实际上就是要检查 $used(j) < c_i$ 的限制。

最终核心代码如下:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) used[j] = 0;

    for (int j = a[i]; j <= m; j++)
        if (!f[j] && f[j - a[i]] && used[j - a[i]] < c[i]) {
            f[j] = true;
            used[j] = used[j - a[i]] + 1;
        }
}

优化掉了一层循环的根本原因在于:这是个可行性判断问题

  1. 原本的多重背包模型,对每个阶段 $i$ 都会跑 $c_i$ 次 $f$ 数组依次进行转移。 因为多重背包模型需要求出 $f(j)$ 的具体取值。但是可行性判断只需要判断真假, 对于每个 $f(j)$ 而言,仅当面值 $j$ 从未被拼成出来时,才考虑转移。只要拼成功过,就不再考虑这个 $j$ 了。

  2. 而每个硬币的使用次数 $c_i$ 的限制,可以使用辅助数组 $used$ 来保证,同时此数组可以随着 $j$ 的循环同步递推。

硬币 - 优化后完整 C++ 代码
#pragma GCC optimize(3)

using namespace std;

const int N = 101;
const int M = 1e5 + 10;
const int C = 1001;

int n, m;
int a[N], c[N];
bool f[M];
int used[M];

int solve() {
    memset(f, 0, sizeof f);
    f[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) used[j] = 0;
        for (int j = a[i]; j <= m; j++)
            if (!f[j] && f[j - a[i]] && used[j - a[i]] < c[i])
                f[j] = true, used[j] = used[j - a[i]] + 1;
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) ans += f[i];
    return ans;
}

简单总结

  1. 四种背包问题模型的代码实现有一定规律,其中 01 背包 和 完全背包是基础。
  2. 多重背包可以看做对每种物品重复执行了多次的 01 背包问题。
  3. 分组背包可以看做在 01 背包基础上,对每个目标体积、对组内每个物品依次推导,取总的最值。
  4. 多重背包问题下,如果不计算具体值,而只判断可行性,可以尝试改造为「受次数限制的完全背包问题」。

(完)


更新日志:

  • 2024/02/12:添加「数组的均值分割」问题
  • 2024/02/06:添加「组合优化」问题,并解释了它和完全背包的区别。
  • 2024/02/22:添加问题「最大约数和」。
  • 2024/02/24:添加问题「砝码称重」、「完全平方数」

本文原始链接地址: https://writings.sh/post/knapsack

王超 ·
喜欢这篇文章吗?
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅