通过背包问题来学习动态规划的思想

骑猪看日落 2023-06-15 07:09 11阅读 0赞

### 目录 ###

*  动态规划介绍
 *  背包问题
 *   *  解决思路
     *  总结规律
     *  代码实现

# 动态规划介绍 #

1.  动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2.  动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
3.  与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4.  动态规划可以通过填表的方式来逐步推进，得到最优解.

# 背包问题 #

有一个背包，容量为4磅 ， 现有如下物品：

1.  要求达到的目标为装入的背包的总价值最大，并且重量不超出
2.  要求装入的物品不能重复

## 解决思路 ##

解决类似的问题可以分解成一个个的小问题进行解决，假设存在背包容量大小分为1，2，3，4的各种容量的背包(分配容量的规则为最小重量的整数倍)：

例如:

第i行表示当前有第1-i个商品可以选择装入背包，第j列表示背包最大容量为j时可以装入的最大价值。

对于第一行(i=1), 目前只有吉他可以选择，所以

对于第二行(i=2),目前存在吉他和音响可以选择,所以

对于第三行(i=3),目前存在吉他和音响、电脑可以选择,所以

## 总结规律 ##

设p(i)、w(i)分别为第i个物品的价值和重量，v(i)(j)表示在前i个物品中能够装入容量为j的背包中的最大价值。

1.  v(i)(0)=v(0)(j)=0
2.  当w(i) > j 时，v(i)(j) = v(i-1)(j)。当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
3.  当w(i) <= j 时，v(i)(j) = max\{v(i-1)(j), p(i) + v(i-1)(j - w(i))\}。当准备加入的新增的商品的容量小于等于当前背包的容量,装入的方式:
    
    v(i-1)(j)：上一个单元格的装入策略的价值，这里可以理解为不装入商品i时的最大价值；
    
    v(i-1)(j - w(i))：装入商品i之后剩下的容量可以装入的最大价值，所以p(i) + v(i-1)(j - w(i))就是装入商品i时的最大价值。

## 代码实现 ##

import numpy as np
    
    
    def knapsack(weight, value, C):
        """ :param weight: 每个商品的重量 :param value: 每个商品的价值 :param C: 背包的最大容量 :return: """
    
        v = np.zeros([len(weight)+1, C+1])  # 存储每个单元格的最大价值
    
        # 存储每个单元格的对应最大价值时选择的商品组合
        goods = np.full([len(weight)+1, C+1], '', dtype='<U30')
    
        for i in range(1, v.shape[0]):
            for j in range(1, v.shape[1]):
                temp = 0
    
                # 最大价值的动态规划
                # v[i-1][j]其实就是不加入商品i时的最大价值
                # temp：加入商品i时的最大价值
                if weight[i-1] > j:
                    v[i][j] = v[i-1][j]
                else:
                    temp = value[i-1] + v[i-1][j - weight[i-1]]
                    v[i][j] = max(v[i-1][j], temp)
    
                # 最佳商品组合，字符串形式，以'_'分割，其实与最大价值的思路一样
                if v[i-1][j] > temp:  # 不加入商品i时的最大价值比加入商品i时的最大价值高
                    goods[i][j] = goods[i-1][j]
                elif v[i-1][j] < temp:  # 不加入商品i时的最大价值比加入商品i时的最大价值低
                    if goods[i-1][j - weight[i-1]] == '':
                        goods[i][j] = str(i - 1)
                    else:
                        goods[i][j] = goods[i-1][j - weight[i-1]] + '_' + str(i-1)
                else:  # 加入商品i时的最大价值比加入商品i时的最大价值相等时，我们取重量较小的
                    w1 = 0
                    w2 = weight[i-1]
                    for g1 in goods[i-1][j].split('_'):
                        w1 += weight[int(g1)]
                    for g2 in goods[i-1][j - weight[i-1]].split('_'):
                        w2 += weight[int(g2)]
                    if w1 < w2:
                        goods[i][j] = goods[i - 1][j]
                    elif w1 > w2:
                        goods[i][j] = goods[i - 1][j - weight[i - 1]] + '_' + str(i - 1)
                    else:  # 如果重量也相等的话，我们将两种组合都记录下来，以'|'分割
                        goods[i][j] = goods[i - 1][j] + '|' + goods[i - 1][j - weight[i - 1]] + '_' + str(i - 1)
    
        print(v)
        print(goods)
    
    
    if __name__ == '__main__':
        weight = [1, 4, 3]
        value = [1500, 3000, 2000]
        knapsack(weight, value, C=4)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]  
欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114601674.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191121202820169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ==,size_16,color_FFFFFF,t_70
[20200430114601674.jpg]: https://img-blog.csdnimg.cn/20200430114601674.jpg