阅读 1369

算法小专栏:动态规划(一)

级别: ★☆☆☆☆
标签:「算法」「DP策略」「动态规划」
作者: MrLiuQ
审校: QiShare团队


本篇将介绍动态规划相关知识。

一、简介

动态规划(Dynamic Programming,简称DP)。

它的核心思想是把一个复杂的大问题拆成若干个子问题,通过解决子问题来逐步解决大问题

注意:使用动态规划思想有个前提:当且仅当每个子问题都是离散的(即每个子问题都不依赖于其他子问题时),才能使用动态规划。


二、动态规划之“0-1背包问题”

现在有这么一个场景, “你”是一名“小偷”,你带了个包去“偷东西”,。

条件1:每个商品只有一个,要么拿,要么不拿。(0-1背包问题) 条件2:你最多拿得动4kg的东西。(固定大小,可不装满)

商品 价格 重量
商品A 3000元 4kg
商品B 2000元 3kg
商品C 1500元 1kg
商品D 2000元 1kg

有限的重量条件下,如何**“偷”**,赚的钱最多?

方案一:简单算法(可行,不推荐)

暴力枚举出所有商品的排列组合, 舍去所有超出重量要求的组合, 从中挑一个最大的。

可行,但是太慢了,每多一件商品都会多2倍的组合。

方案测评:时间复杂度 O(2n),超级超级慢,不推荐。

方案二:贪心算法(不可行)

用上篇介绍的贪心算法计算。

通过某个贪心策略(拿最贵的、拿性价比最高的商品)来得出近似解。

方案测评:这种方案接近最优解,是近似解,但不一定是最优解,故不可行。

方案三:动态规划(可行,推荐)
  • 原理:先解决子背包最优,再解决大背包最优。

先绘制出一张表格,一会我们一列一列慢慢填。(PS:体会动态规划的算法过程)

表格:(实际上对应了一个二维数组)

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A
商品B
商品C
商品D

先解读一下这个表格, 行:代表了商品行(对应i), 列:代表了重量列(对应j), 格:代表当前的已有的商品、已有重量下所能拿的最大价值

好了,下面我们开始一列一列的填:

第一行,只有商品A(价值:3000,重量:4kg)

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A /
商品B
商品C
商品D

第二行,有商品A(价值:3000,重量:4kg)与商品B(价值:2000,重量:3kg)

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A /
商品B /
商品C
商品D

第三行,有商品A(价值:3000,重量:4kg)、商品B(价值:2000,重量:3kg)商品C(价值:1500,重量:1kg)

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A /
商品B /
商品C 1500
商品D

第四行,有商品A(价值:3000,重量:4kg)、商品B(价值:2000,重量:3kg)、商品C(价值:1500,重量:1kg)、商品D(价值:2000,重量:1kg)

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A /
商品B /
商品C 1500
商品D 2000

大家有没有发现,这里填写每个表格时的算法可表示为:

对应行的商品的重量超过当前子背包的重量,就取上一行单元格的值, 商品的重量能装下当前子背包,则取下面两者的较大值:

  • 上一个单元格的值(cell[i-1][j]
  • 当前商品的价值 + 剩余空间的价值(cell[i-1][j-当前商品的重量所对应的列号]

下面填第二列:

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A / /
商品B / /
商品C 1500 1500
商品D 2000 3500

第三列:

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A / / /
商品B / / 2000
商品C 1500 1500 2000
商品D 2000 3500 3500

第四列:

商品\ 子背包最大重量 1kg 2kg 3kg 4kg
商品A / / / 3000
商品B / / 2000 3000
商品C 1500 1500 2000 3500
商品D 2000 3500 3500 4000

于此反复判断即可,这样每个单元格都是最优解,通过解决子问题,推导出最终最优解。 这就是动态规划,是不是很简单呢?

转换成Python代码:

def package_dp(a, b, flag, n):
    c = [[0 for i in range(n)] for j in range(n)]
    for j in range(n):
        c[0][j] = 0

    for i in range(n):
        c[i][0] = 0
        for j in range(n):
            if b[i]>flag[j]:
                c[i][j] = c[i-1][j]
            else:
                temp1 = a[i] + c[i-1][j-b[i]]
                temp2 = c[i-1][j]
                c[i][j] = max(temp1,temp2)
            print c[i][j]
        print ("")
    return c

price = [0, 3000, 2000, 1500, 2000]
weight = [0, 4, 3, 1, 1]
flag = [0, 1, 2, 3, 4]

package_dp(price, weight, flag, 5)
复制代码

三、细节问题

  • 子背包拆分问题:按照 所有商品 的最大公约数(也有可能存在小数)去拆子背包。 让所有的商品都能被刚好装下。

  • 通过子背包的最优解 => 推导出 => 全背包的最优解。 这个过程的思想,就是DP思想(动态规划的核心思想)


四、动态规划的应用场景

本文举了背包与矩阵连乘的例子,其实思路都是一样的。 只是应用场景不同,常见的应用场景有以下几个:

  • 0-1背包问题( ✔️)
  • 矩阵连乘法( ✔️)
  • 硬币找零
  • 字符串相似度
  • 最长公共子序列
  • 最长递增子序列
  • 最大连续子序列和/积
  • 有代价的最短路径
  • 瓷砖覆盖(状态压缩DP)
  • 工作量划分

参考资料:


小编微信:可加并拉入《QiShare技术交流群》。

关注我们的途径有:
QiShare(简书)
QiShare(掘金)
QiShare(知乎)
QiShare(GitHub)
QiShare(CocoaChina)
QiShare(StackOverflow)
QiShare(微信公众号)

推荐文章:
Dart基础(一)
Dart基础(二)
Dart基础(三)
Dart基础(四)
iOS 短信验证码倒计时按钮
iOS 环境变量配置
iOS 中处理定时任务的常用方法
奇舞周刊

关注下面的标签,发现更多相似文章
评论