前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【动态规划/背包问题】从数学角度推导「完全背包」与「01 背包」之间的遍历顺序关系

【动态规划/背包问题】从数学角度推导「完全背包」与「01 背包」之间的遍历顺序关系

作者头像
宫水三叶的刷题日记
发布2021-06-23 10:46:56
7940
发布2021-06-23 10:46:56
举报

前言

今天是我们讲解「动态规划专题」中的 「背包问题」的第四天

在众多背包问题中「01 背包问题」是最为核心的,因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。

其中 01 背包的「一维空间优化」更是要重点掌握。

另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。

你也先可以尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~

题目描述

N

种物品和一个容量为

C

的背包,每种物品都有无限件。

i

件物品的体积是

v[i]

,价值是

w[i]

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

其实就是在 0-1 背包问题的基础上,增加了每件物品可以选择多次的特点(在容量允许的情况下)。

示例 1:

代码语言:javascript
复制
输入: N = 2, C = 5, v = [1,2], w = [1,2]
输出: 5
解释: 选一件物品 1,再选两件物品 2,可使价值最大。

常规解法

我们可以直接将 01 背包的「状态定义」拿过来用:

dp[i][j]

代表考虑前

i

件物品,放入一个容量为

j

的背包可以获得的最大价值。

由于每件物品可以被选择多次,因此对于某个

dp[i][j]

而言,其值应该为以下所有可能方案中的最大值:

  • 选择 0 件物品
i

的最大价值,即

dp[i-1][j]
  • 选择 1 件物品
i

的最大价值,即

dp[i-1][j-v[i]]+w[i]
  • 选择 2 件物品
i

的最大价值,即

dp[i-1][j-2*v[i]]+2*w[i]

...

  • 选择 k 件物品
i

的最大价值,

dp[i-1][j-k*v[i]]+k*w[i]

由此我们可以得出「状态转移方程」为:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * v[i]] + k * w[i]), 0 < k*v[i] \leqslant j

代码:

代码语言:javascript
复制
class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[N][C + 1];
        
        // 先预处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然当只有一件物品的时候,在容量允许的情况下,能选多少件就选多少件
            int maxK = j / v[0];
            dp[0][j] = maxK * w[0];
        }
        
        // 处理剩余物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况(选择 0 件物品 i)
                int n = dp[i - 1][j];
                // 考虑第 i 件物品的情况
                int y = 0;
                for (int k = 1 ;; k++) {
                    if (j < v[i] * k) {
                        break;
                    }
                    y = Math.max(y, dp[i - 1][j - k * v[i]] + k * w[i]);
                }
                dp[i][j] = Math.max(n, y);
            }
        }
        return dp[N - 1][C];
    }
}
  • 时间复杂度:共有
N * C

个状态需要被转移,但每次转移都需要枚举当前物品的件数,最多枚举 C 次(重量为最小值 1),因此整体复杂度为

O(N * C * C)
  • 空间复杂度:
O(N * C)

「滚动数组」解法

通过观察我们的「状态转移方程」可以发现,我们在更新某个

dp[i][x]

的时候只依赖于

dp[i-1][x]

因此我们可以像 01 背包那样使用「滚动数组」的方式将空间优化到

O(C)

代码:

代码语言:javascript
复制
class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[2][C + 1];
        
        // 先预处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然当我们只有一件物品的时候,在容量允许的情况下,能选多少件就选多少件
            int maxK = j / v[0];
            dp[0][j] = maxK * w[0];
        }
        
        // 处理剩余物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况(选择 0 件物品 i)
                int n = dp[(i - 1)&1][j];
                // 考虑第 i 件物品的情况
                int y = 0;
                for (int k = 1 ;; k++) {
                    if (j < v[i] * k) {
                        break;
                    }
                    y = Math.max(y, dp[(i - 1)&1][j - k * v[i]] + k * w[i]);
                }
                dp[i&1][j] = Math.max(n, y);
            }
        }
        return dp[(N - 1)&1][C];
    }
}
  • 时间复杂度:共有
N * C

个状态需要被转移,但每次转移都需要枚举当前物品的件数,最多枚举 C 次(重量为最小值 1),因此整体复杂度为

O(N * C * C)
  • 空间复杂度:
O(N * C)

「一维空间优化」解法

我们知道在 01 背包中,最重要的是「一维空间优化」解法。

之所以 01 背包能够使用「一维空间优化」解法,是因为当我们开始处理第

i

件物品的时候,数组中存储的是已经处理完的第

i - 1

件物品的状态值。

然后配合着我们容量维度「从大到小」的遍历顺序,可以确保我们在更新某个状态时,所需要用到的状态值不会被覆盖。

因此 01 背包问题的状态转移方程为:

dp[j] = max(dp[j], dp[j - v[i]] + w[i])

同时容量维度的遍历顺序为从大到小。

PS. 如果你不太理解上面的话,或许是因为你「还没学习」或者「有点忘记」01 背包问题,三叶强烈建议你先对 01 背包问题 进行学习/回顾。

而「完全背包」区别于「01 背包」,在于每件物品可以被选择多次。

因此你可能会在别的地方看到这样的讲解:

「01 背包将容量维度「从大到小」遍历代表每件物品只能选择一件,而完全背包将容量维度「从小到大」遍历代表每件物品可以选择多次。」

这样的解释其实是利用了人的抽象思维,但感觉不一定是对的。

接下来,我们从「数学」的角度去证明为什么修改 01 背包的遍历顺序可以正确求解完全背包问题。

我们先来展开完全背包中

dp[i][j]

的所有可能方案:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i],...,dp[i - 1][j - k * v[i]] + k * w[i]), 0\leqslant k*v[i] \leqslant j
dp[i][j]

所代表的含义:在容量允许的情况下,对于第

i

件物品,我们可以不选,可以选 1 次,可以选 2 次,...,可以选

k

次 ...

然后我们通过代入,看看

dp[i][j - v[i]]

是什么内容:

dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 * v[i]] + w[i], dp[i - 1][j - 3 * v[i]] + 2 * w[i],...,dp[i - 1][j - k * v[i]] + (k - 1) * w[i]), 0\leqslant k*v[i] \leqslant j

光看公式可能很难看出两者的联系,三叶将相同的部分进行标记:

总结一下。

  • 0-1 背包问题的状态转换方程是:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

由于计算

dp[i][j]

的时候,依赖于

dp[i - 1][j - v[i]]

因此我们在改为「一维空间优化」时,需要确保

dp[j - v[i]]

存储的是上一行的值,即确保

dp[j - v[i]]

还没有被更新,所以遍历方向是从大到小。

  • 完全背包问题的状态转移方程是:
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])

由于计算

dp[i][j]

的时候,依赖于

dp[i][j - v[i]]

因此我们在改为「一维空间优化」时,需要确保

dp[j - v[i]]

存储的是当前行的值,即确保

dp[j - v[i]]

已经被更新,所以遍历方向是从小到大。

代码:

代码语言:javascript
复制
class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况(选择 0 件物品 i)
                int n = dp[j];
                // 考虑第 i 件物品的情况
                int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; 
                dp[j] = Math.max(n, y);
            }
        }
        return dp[C];
    }
}
  • 时间复杂度:共有
N * C

个状态需要被转移,复杂度为

O(N * C)
  • 空间复杂度:
O(C)

总结

今天我们学习了【动态规划/背包问题】中的「完全背包」问题。

形式上,我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。

但本质是因为两者进行状态转移时依赖了不同的格子:

  • 01 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
  • 完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。

另外,我们可以发现通过「一维空间优化」方式,可以将求解「完全背包」问题的时间复杂度从

O(N * C * C)

降低为

O(N*C)

这就是为什么三叶一直强调 01 背包问题的「一维空间优化」解法是几乎所有背包问题的基础。

背包问题(目录)

  1. 01背包 : 背包问题 第一讲
    1. 【练习】01背包 : 背包问题 第二讲
    2. 【学习&练习】01背包 : 背包问题 第三讲
  2. 完全背包 : 本篇
    1. 【练习】完全背包
  3. 多重背包
    1. 【练习】多重背包
  4. 多重背包(优化篇)
    1. 【练习】多重背包(优化篇)
    2. 【练习】多重背包(优化篇)
  5. 混合背包
    1. 【练习】混合背包
  6. 分组背包
    1. 【练习】分组背包
  7. 多维背包
    1. 【练习】多维背包
  8. 树形背包
    1. 【练习篇】树形背包
  9. 背包求方案数
    1. 【练习】背包求方案数
  10. 背包求具体方案
    1. 【练习】背包求具体方案
  11. 泛化背包
    1. 【练习】泛化背包

最后

这是我们「刷穿 LeetCode」系列文章的第 No.* 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-04-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 题目描述
  • 常规解法
  • 「滚动数组」解法
  • 「一维空间优化」解法
  • 总结
  • 背包问题(目录)
  • 最后
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档