--- title: "完全背包问题" created: 2025-11-28 tags: - 算法 --- # 完全背包问题 ## 题目 [完全背包问题](https://www.acwing.com/problem/content/3/) ![[image-74d321b4.png]] ## 思路分析 小明期末考试得了全班第一名，妈妈给了他一个背包，可以去超市任意选购，可以选购多种商品，每种商品可以选购多个，但是选择的商品必须都放在背包里。 超市很大，有很多种商品：火腿，雪糕，饼干 ·····。每种商品都摆满了货架。不同商品的体积和价值不同。 在背包能装下的前提下，小明想尽可能带回价值总量高的商品，请问他能带回的商品的最大价值是多少？ 这就是完全背包问题。 有 N 种物品和一个背包，每种物品的数量无限。给出了每种物品的体积 v 和价值 w 以及背包的容量 V。 求解 : 背包能装下的前提下，所能获得的最大价值。 例如我们有 4 种物品和一个容量为 5 的背包。 这四种物品对应的体积和价值分别是： 物品一：体积是 1，价值是 2。 物品二：体积是 2，价值是 4。 物品三：体积是 3，价值是 4。 物品四：体积是 4，价值是 5。 我们可以选择把 1 个 物品一 和 1 个 物品四 放入背包，体积是 1 + 4 = 5，没有超过背包容量，价值是 2 + 5 = 7。 我们可以选择把 1 个 物品一 和 2 个 物品二 放入背包，体积是 1 + 2 + 2 = 5，没有超过背包容量，价值是 2 + 4 + 4 = 10。 我们可以选择把 2 个 物品一 和 1 个 物品三 放入背包，体积是 1 + 1 + 3 = 5，没有超过背包容量，价值是 1 + 1 + 4 = 6。 还有其它选法。 我们的目的是，找到能被背包装下的物品的最大价值。 **与01不同的是 同一样物品可以选多次** 用闫氏dp分析法来看 ![[image-5f4dbcff.png]] 从三个步骤进行考虑。 **步骤一:集合和集合的状态** 所谓的集合，就是一些方案的集合。 用 g[i][j] 表示从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。注意：g[i][j] 不是一个数，是一堆数。 例如 g[2][3] 从前 2 种物品中进行选择，且总体积不大于 3 的各个选法获得的价值的集合。 g[2][3] 的可选择方案包括： 方案一：都不选，总价值为 0。 方案二：选 1 件 物品 1，总价值为 2。 方案三：选 2 件物品 1，总价值为 4。 方案四：选 3件 物品 1，总价值为 6。 方案五：选 1 件物品 2，总价值为 4。 方案六：选 1 件物品 2，一件物品 1，总价值为 6。 所以 g[2][3] = {0，2，4，6，4，2}。 i j 取不同的值，对应不同的 g[i][j]，也就是对应不同的集合。 用 f[i][j] 表示从前 i 种物品中进行选择，总体积小于等于 j 所能获得的**最大价值**。 很明显，f[i][j] 就是 g[i][j] 中的最大值。 i j 取不同的值，就对应不同的 f[i][j]。 我们把 f[i][j] 叫做集合的状态。 例如 f[2][3] 表示从前 2 种物品中进行选择，且总体积不大于 3 的获得的最大价值。 f[2][3] = max(g[2][3] ) = max( 0，2，4，6，4，2) = 6。 g[i][j] 的最大值就是 f[i][j]。 如果我们能把所有集合对应的最大值都求出来，即求出了 f[0][0] ~ f[N][V]， f[N][V] 的含义是在前 N 种物品中进行选择，总体积不大于 V 所获得的最大价值，就是我们要找的答案。 ![[image-55069e9d.png]] 注意，我们不需要把各个集合的所有元素都找出来，只需要求出各个集合的最大值，就能找到答案。下面就是如何求出各个集合的最大值。 **步骤二：状态计算** g[i][j] 是从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。 f[i][j] 是从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。 f[i][j] 是集合 g[i][j] 的最大值。 ![[image-18f076ff.png]] 所谓的状态计算是指，如何将把 f[i][j] 算出来。 如果把各个集合 g[i][j] 的状态 f[i][j] 求出来， f[N][V] 就是要找的答案。 回想一下 0 1 背包问题。 01 背包问题把 g[i][j]划分成了 A B 两部分，分别求出这两个部分对应的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，就是 f[i][j]。 01 背包根据是否选择第 i 件物品，也就是第 i 件物品选 0 个还是 1 个，把 g[i][j] 划分成了 A B 两部分，分别求出这两个部分的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。 完全背包问题也是根据第 i 件物品的选择数量，把 g[i][j] 划分成不同的部分，分别求出各个部分的最大值，取各个部分最大值中的最大值，就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。 因为每种物品的数量是无限的，根据第 i 种物品的选择数量可以把 g[i][j] 分为这样几部分： A 部分： 第 i 种物品选 0 件。 B 部分：第 i 件物品选 1 件。 C 部分： 第 i 件物品选 2 件。 X 部分： 第 i 件物品选 x 件。 ![[image-50c7871e.png]] 因为选择物品的总体积不能大于j，所以第 i 件物品最多选 j / vi 向下取整 件。 对于 A 部分： 第 i 件物品选 0 件。 等价于从前 i - 1 种物品中选择商品，且总体积不超过 j 的各个价值的集合，也就是 g[i - 1][j]。 g[i - 1][j] 这个集合中的最大值是 f[i - 1][j] ，所以 A 部分的最大值就是 f[i - 1][j]。 对于 B 部分： 第 i 件物品选 1 件， 1 个 i 物品会占据 vi的背包空间，剩下的背包空间为 j - vi 。 可以从前 i - 1 种物品中，选出总体积小于等于j - vi 的物品放入背包。 从前 i - 1 种物品中，选出总体积小于等于j - vi 的各个方案获得的价值集合为 g[i - 1][j - vi ]，所以 B 部分的元素为 g[i - 1][j - vi ] 中各个元素加上 wi 。 g[i - 1][j - vi ] 中的最大值为 f[i - 1][j - vi ]，所以 B 部分的最大值为 f[i - 1][j - vi ] + wi。 对于 X 部分： 第 i 件物品选 x 件， x 个 i 物品会占据 x \* vi 的背包空间，剩下的背包空间为 j - x \* vi 。 可以从前 i - 1 种物品中，选出总体积小于等于j - x \* vi 的物品放入背包。 从前 i - 1 种物品中，选出总体积小于等于j - x \* vivi 的各个方案获得的价值集合为 g[i - 1][j - x \* vi ]， 所以 x 部分的元素为 g[i - 1][j - x \* vi ] 中各个元素加上 x \* wi 。 g[i - 1][j - x \* vivi ] 中的最大值为 f[i - 1][j - x \* vi ]， 所以 B 部分的最大值为 f[i - 1][j - x \* vi ] + x \* wi。 例如 g[2][4]。 第二种物品的体积为 2，选择物品的总体积不能超过 4。 所以第二件物品可以选择：0件、1件、2件。 因此 g[2][4] 可以分成以下几部分： A 部分：第二件物品选 0 件。A 部分的最大值为： f[i - 1][j - 0 \* vi] + 0 \* wi 。 B 部分：第二件物品选 1 件。B部分的最大值为： f[i - 1][j - 1 \* vi ] + 1 \* wi 。 C 部分：第二件物品选 2 件。C 部分的最大值为：f[i - 1][j - 2 \* vi ] + 2 \* wi 。 g[2][4] 中的最大值为 max(A，B，C)。 通过上面分析，我们可以知道，g[i][j] 可以分成若干部分: A 部分是第 i 种物品选 0 个对应所有选法获的价值的集合，最大值是 f[i - 1][j]。 B 部分是第 i 种物品选 1 个对应所有选法获的价值的集合，最大值是 f[i-1][j - vi] + wi。 X 部分是第 i 种物品选 x 个对应所有选法获的价值的集合，最大值是 f[i - 1][j - x \* vi]+x\*wi。 所以 g[i][j] 的最大值就是所有子集的最大值中最大的那个，也就是 f[i][j] = max(A, B ，····) 即： 展开式为： f[i] [j] = max( f[i-1][j] , f[i - 1][j - vi]+w , f[i - 1][j - 2 \* vi] + 2 \* w , f[i - 1][j - k \* vi ] + k \* w , …..) 其中 k <= j / w。 从计算公式可以看出: f[i][j] 是由 f[i - 1][j - k \* vi ] (0 <= k <= j / wi) 和 wi 计算出来的。 f[i][j]的值是可以从前面已经计算出的 f 值求出来。 如果我们能确定 f[i][j] 的一部分初始值，就能通过该公式，一步步计算得出 f[N][V]，也就是我们要找的答案。 **步骤三：确定初始值** 完全背包问题的有些状态是能够直接确定的。 例如 f[0][0]。 f[0][0] 的含义是: 从前 0 种物品中选择，并且选出的物品总体积小于等于0 时所能得到的最大价值。 总体积小于等于 0，说明一种物品都不能选择。 因此 f[0][0] = 0。同理 f[1][0] = 0，f[2][0] = 0 ··· f[N][0] = 0。 有了这些初始值，通过 i 从 1 遍历 N，j 从 1 遍历 V，第 i 种物品的选择数量 k 从 0 遍历到 j / wi 就能一步步求出所有的 f[i][j] 了。 例如求 f[1][1]： f[1][1] = max{f[0][1]，f[0][0] + 2} = max(0，2) = 2。 求 f[1][2]： f[1][2] = max{f[0][2]，f[0][1] + 2，f[0][0] + 4} = max(0，2，4) = 4。 最后 f[N][V] 就是要找的答案。 **首先朴素地去写** 不外乎就是添加了一个条件 对于每个物品我可能放多次 那就枚举一下 该物品不放 到 该物品放最大可放数量 的各种情况 ```cpp #include using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = 0; j <= m; j ++ ) //其实就是在01的基础上 加上一个遍历每个物品放多少次的循环 for(int k = 0; k * v[i] <= j; k ++ )//可以无限取 但不能超过剩余容量 f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); //f[i-1][j]包含在后半部分 即k=0的时候 cout << f[n][m] << endl; } ``` **去除第三层循环的优化** ![[image-123ec702.png]] ```cpp #include using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = 0; j <= m; j ++ ) /* 三重循环会tle 试着把这层循环去掉 for(int k = 0; k * v[i] <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); 把k=1 2 3……代入 f[i,j] = Max(f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w...) f[i,j-v] = Max( f[i-1,j-v] , f[i-1,j-2v]+w , f[i-1,j-3v]+2w...) 可以发现从 f[i,j-v] -> f[i,j] 有很多项相似 也就是说 加入第i个物品 状态变化有规律可言 （本来就是要依靠子问题去更新当前问题的答案 所以提取出上一层与当前层的关系 状态转移方程就好写了） 规律就是 f[i,j]其实就是除第一项外 其他项为f[i,j-v]+w (每一项比原本多了一个w罢了) 那么状态转移方程就可以写成：f[i,j] =Max(f[i-1,j],f[i,j-v]+w) 这样一来就又变成了01背包问题类似的代码 所以得加上个判断 可放入的情况和不可放入的情况 */ { //不可放入的情况 直接用上一级答案 f[i][j] = f[i-1][j]; //可放入的情况 if(j>=v[i]) //将找到的规律变形 第一项没规律，保留 其他项有规律 为上一级+w f[i][j] =max(f[i-1][j], f[i][j - v[i]] + w[i]); //f[i][j] =max(f[i][j], f[i][j - v[i]] + w[i]);(前面有f[i][j] = f[i-1][j];) } cout << f[n][m] << endl; } ``` 那么可以发现 现在的核心代码和01背包问题的非常相似了 `f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包` `f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题` 唯一的区别在于 01背包是从上一层i-1的状态得来 而完全背包是从这一层的i的状态得来 那么同样也可以用滚动数组优化 这次要的是滚动后覆盖后的值 所以可以从小到大枚举 ```cpp #include using namespace std; const int N = 1010; int v[N],w[N]; int f[N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = v[i]; j <= m; j ++ )//要的是第i层的覆盖后的j-v[i] 所以从小到大枚举 f[j] = max(f[j], f[j-v[i]] + w[i]); cout << f[m] << endl; } ``` **所以到最后 发现和01背包问题只有一个地方不一样——体积是从小到大遍历还是从大到小遍历** **而究其原因 就在于 要的是第i-1层的未被覆盖的数据 还是第i层的覆盖后的数据** **从大到小是未覆盖的值 从小到大是覆盖后的值** ## 代码实现 朴素实现 O(n\*m^2) TLE ```cpp #include using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = 0; j <= m; j ++ ) for(int k = 0; k * v[i] <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); cout << f[n][m] << endl; } ``` 去除第三层循环的优化 ```cpp #include using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ){ for(int j = 0; j <= m; j ++ ){ f[i][j] = f[i-1][j]; if(j>=v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]); } } cout << f[n][m] << endl; } ``` 滚动数组优化 ```cpp #include using namespace std; const int N = 1010; int v[N],w[N]; int f[N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = v[i]; j <= m; j ++ )//要的是第i层的覆盖后的j-v[i] 所以从小到大枚举 f[j] = max(f[j], f[j-v[i]] + w[i]); cout << f[m] << endl; } ``` ## 同类题型 ## 视频讲解 --- ⬅️ [[货币系统|货币系统]] 🏠 [[00-刷题理模型]] ➡️ [[有依赖的背包问题|有依赖的背包问题]]