算法学习:动态规划

发布于 / 算法学习 / 0 条评论

基本动态规划

动态规划 (Dynamic Programming) 是运筹学的一个分支,是求解决策过程最优化的数学方法。

以下内容学习自《算法图解》

实例背景:

假如有一个小偷,他的背包大小确定,假设为4磅。他有以下三件物品可以偷窃:

待“偷”物

音响(S) 笔记本电脑(L) 吉他(G)
3000美元 2000美元 1500美元
4磅 3磅 1磅

为了让偷窃价值最高,他该偷窃哪些内容呢?

  • 方法一:枚举出每一种情况,然后比较每一种情况所能得到的货物的总价值。具体如下图所示:

    暴力方法

    当有3件物品时,我们需要罗列出8种情况。而当4件物品时就需要罗列16种情况;5件物品就需要32种情况,也就是说这样的求解方法的时间复杂度达到了O(2^n)

  • 方法二:动态规划

    对于大的背包,我们可以先将其分解为一个个小的背包来考虑,最后用小的背包的情况来推知大的背包的最佳情况。

    开始动态规划思想

    那么我们就会得到如下的一个表格:

类别 1 2 3 4
吉他
音响
笔记本电脑
从左到右分别为**1磅背包**、**2磅背包**、**3磅背包**、**4磅背包**的情况,然后我们从第一行开始对表格进行填充:
  • 吉他行

    对于每一格,这个小偷都要考虑一个问题:“我到底要不要偷这个东西?”

    对于第一个格,它的背包容量为1磅,所以我可以将吉他装下,所以他肯定是要偷的啦~ 于是表格就会更新成下面的这个样子:

    类别 1 2 3 4
    吉他 $1500 (G)
    音响
    笔记本电脑

    而对于之后的每个格,因为现在只有吉他可以偷,而这些包都可以放下吉他,所以我们就将这些格的内容更新如下:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响
    笔记本电脑

    那这小偷既然可以直接推知四磅的情况,为什么还要记录1磅、2磅、3磅的情况呢?因为这些小问题将为解决后面的大问题作铺垫!😀

  • 音响行

    在第二行,我们可以偷的东西变成了吉他和音响,其上面一行记录了我们是否应该偷吉他以及已经获得了的价值最大值。那么我们结合它的上一行来判断是否需要偷音响。

    对于第一格,无论怎样都装不下音响,所以继承了上一行的吉他的总价值,列表变成如下:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G)
    笔记本电脑

    相同的,2磅与3磅时也装不下音响(这音响居然这么大🌚),所以表格变成了:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G) $1500 (G) $1500 (G)
    笔记本电脑

    对于4磅时,音响可以装下了,那么他要不要偷这个音响呢?如果偷音响的话,那么我获得的价值将会是dp[0][0] + v[1]dp[x][y]指列表中第x行第x列的元素(其中在上面的列表中第x列忽略,值全部为0),v[i]指第i件物品待偷物的价值),可得到值为 \$3000,如果不偷这个音响,则最后值为dp[0][4],可到的值为 \$1500,所以得出结论还是偷音响好。得到如下的列表:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G) $1500 (G) $1500 (G) $3000 (S)
    笔记本电脑
  • 笔记本电脑行

    从音响一行已经可以了解到,有以下式子的成立:(h[x] 指的是第 x 可被偷物的质量/体积)
    dp[i][j] = max(dp[i – 1][j – h[x]]+v[x] , dp[i – 1][j])
    所以根据这个公式,我们可以轻而易举的来填写笔记本电脑这一行,得到如下的列表:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G) $1500 (G) $1500 (G) $3000 (S)
    笔记本电脑 $1500 (G) $1500 (G) $2000 (L) $3500 (G&L)

    举最后一格来解释:4磅的空间已经可以放下笔记本电脑,如果不偷笔记本电脑的话,我将得到dp[1][4]的价值,值为 \$3000。如果他偷笔记本电脑的话,我就可以获得dp[1][4 - 3] + v[2] = dp[1][1] + v[2]的价值,值为 \$ 3500。取更大的,我们就可以知道这一格应为 \$ 3500

现在表格全部填写完毕了,最右下方的格子即为最终答案:\$ 3500

  • 再加一件商品又是如何呢?

    假如小偷现在又发现了一个新鲜玩意儿:iPhone!(I)(这东西这么贵肯定要偷的啊🤪

    轻而更贵的东西

    那我们需要重新计算整个表格么?不需要!这也是动态规划的一大优点,我逐步计算出了前面的最大价值,那么再有新的元素出现,前面的数据依旧是可以用的!

    那么我们的列表多出一行,成为以下的样子:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G) $1500 (G) $1500 (G) $3000 (S)
    笔记本电脑 $1500 (G) $1500 (G) $2000 (L) $3500 (G&L)
    iPhone

    从第一个格开始计算,这个iPhone太小了啊,1磅的空间就可以将它装下,所以此时第一个格就面临着要不要偷iPhone的抉择。如果不偷的话,就是dp[2][1],值为 \$ 1500。如果偷,就是dp[2][1 - h(3)] + v[3] = dp[2][0] + v[3],值为 \$ 2000。所以看来偷iPhone是个更好的选择!现在表格就成了:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G) $1500 (G) $1500 (G) $3000 (S)
    笔记本电脑 $1500 (G) $1500 (G) $2000 (L) $3500 (G&L)
    iPhone $2000 (I)

    依次以上面的方法对表格进行填充,最终表格成为:

    类别 1 2 3 4
    吉他 $1500 (G) $1500 (G) $1500 (G) $1500 (G)
    音响 $1500 (G) $1500 (G) $1500 (G) $3000 (S)
    笔记本电脑 $1500 (G) $1500 (G) $2000 (L) $3500 (G&L)
    iPhone $2000 (I) $3500 (G&I) $3500 (G&I) $4000 (L&I)

    所以此时的最大值就变成了 \$ 4000,更多了呢!🤑

从以上内容可以看出,动态规划真的是一个神奇好用的算法呢!

那么怎么敲它的代码呢?

C++

int w[5] = {0, 1, 4, 3, 1}; // 每个物品的重量,w[0]无用
int p[5] = {0, 1500, 3000, 2000, 2000}; // 每个物品的价值,p[0]无用
int n = 4; // 物品的个数
int m = 4; // 背包的载重量

vector<int> x; // 用以记录所有的被装入背包的物品
int v = 0;
int dp[5][5]; // 注意多出一行一列
int dp_funtion(){
    for (int i = 0; i < n + 1; i++){
        for (int j = 0; j < m + 1; j++){
            if(j >= w[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
            else dp[i][j] = dp[i - 1][j];
        }
    }
    int j = m;
    for (int i = n; j > 0; j++){
        if (dp[i][j] > dp[i - 1][j]){
            x.push_back(i);
            j = j - w[i];
        }
    }
    return dp[n][m];
}

Python

# 这里使用了图解中的吉他,音箱,电脑,手机做的测试,数据保持一致
w = [0, 1, 4, 3, 1]   #n个物体的重量(w[0]无用)
p = [0, 1500, 3000, 2000, 2000]   #n个物体的价值(p[0]无用)
n = len(w) - 1   #计算n的个数
m = 4   #背包的载重量

x = []   #装入背包的物体,元素为True时,对应物体被装入(x[0]无用)
v = 0
#optp[i][j]表示在前i个物体中,能够装入载重量为j的背包中的物体的最大价值
optp = [[0 for col in range(m + 1)] for raw in range(n + 1)]
#optp 相当于做了一个n*m的全零矩阵的赶脚,n行为物件,m列为自背包载重量

def knapsack_dynamic(w, p, n, m, x):
    #计算optp[i][j]
    for i in range(1, n + 1):       # 物品一件件来
        for j in range(1, m + 1):   # j为子背包的载重量,寻找能够承载物品的子背包
            if (j >= w[i]):    # 当物品的重量小于背包能够承受的载重量的时候,才考虑能不能放进去
                optp[i][j] = max(optp[i - 1][j], optp[i - 1][j - w[i]] + p[i])
                # optp[i - 1][j]是上一个单元的值, optp[i - 1][j - w[i]]为剩余空间的价值
            else:
                optp[i][j] = optp[i - 1][j]

    #递推装入背包的物体,寻找跳变的地方,从最后结果开始逆推
    j = m
    for i in range(n, 0, -1):
        if optp[i][j] > optp[i - 1][j]:
            x.append(i)
            j = j - w[i]  

    #返回最大价值,即表格中最后一行最后一列的值
    v = optp[n][m]
    return v

区间DP

区间DP就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上的最优解的DP算法。

首先枚举区间长度len为每次分割成的小区间长度(由长到短不断合并),内层枚举该长度下的起点。然后在这个起点与中点之间枚举分割殿,求解这段小区间在某个分割点下的最优解。

for(int len = 1; len <= n; len++){//枚举长度
    for(int j = 1; j + len <= n+1; j++){//枚举起点,ends<=n
        int ends = j + len - 1;
        for(int i = j; i < ends; i++){//枚举分割点,更新小区间最优解
            dp[j][ends] = min(dp[j][ends], dp[j][i] + dp[i+1][ends] + something); 
            // something替换
        }
    }
}
转载原创文章请注明,转载自: KONGJUNE » 算法学习:动态规划
Not Comment Found