动态规划算法

╰+哭是因爲堅強的太久メ 2021-07-24 22:41 571阅读 0赞

# 一 动态规划算法 #

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

动态规划可以通过填表的方式来逐步推进，得到最优解。

# 二 背包问题 #

背包问题可以通过动态规划算法来实现。

背包问题：

有一个背包，容量为4磅，现有如下物品。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

1 要求达到的目标为装入的背包的总价值最大，并且重量不超出。

2 要求装入的物品不能重复。

# 三 用填表法解决背包问题 #

> 说明

i：行坐标，代表物品。

j：列坐标，代表物品的容量。

v\[i\]\[j\]：前 i 个物品中能够装入容量为j的背包中的最大价值。

装入顺序是从上到下，从左到右。

> 填表过程

1 可以分析出v\[i\]\[0\]=v\[0\]\[j\]=0，我们先把这些0填入上面的表格。用红色表示。

2 再考虑放吉他，因为它的容量是1磅，所以1磅，2磅，3磅，4磅的背包都可以将吉他放下，我们将吉他的价值填入。用绿色表示。

3 其次考虑放音响，因为它的容量是4磅，1磅，2磅，3磅的背包是放不下它的，所以它们对应的最大价值从上一行拷贝过来，我们用天蓝色表示。4磅的背包可以放下音响，放下音响后，就没剩余空间了，不能再放其它物品。因为它的价值3000大于吉他的价值1500，所以这里就放3000，我们依然用黑色表示。

4 最后我们考虑放电脑，因为它的容量是3磅，1磅，2磅的背包是放不下它的，它们对应的最大价值从上一行拷贝过来，我们用天蓝色表示。3磅的背包可以放下电脑，放下电脑后，就没剩余空间了，不能再放其它物品。因为它的价值2000大于吉他的价值1500，所以这里就放2000，我们依然用黑色表示。

5 4磅的背包可以放下电脑，放完电脑后，背包剩下的空间是1磅，1磅的空间最大可以放价值为1500的吉他，两个加起来是3500，大于上1行的3000，所以这里填写3500，我们用桔色表示。

# 四 背包问题的思路 #

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。

其中又分01背包和完全背包。

*  完全背包：每种物品可以放多次。
 *  01背包：每个物品最多放一个。

无限背包可以转化为01背包。

> 算法的主要思想

利用动态规划来解决。每次遍历到的第i个物品，根据w\[i\]和v\[i\]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v\[i\]、w\[i\]分别为第i个物品的价值和重量，C为背包的容量。

令v\[i\]\[j\]表示在前 i 个物品中能够装入容量为j的背包中的最大价值。

可以推出下面的结论：

## 1 v\[i\]\[0\]=v\[0\]\[j\]=0; ##

表示填入表第一行和第一列是0。

## 2 当w\[i\] > j 时：v\[i\]\[j\]=v\[i-1\]\[j\]    ##

该公式描述的是：当准备加入商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略。

## 3 当j >=w\[i\]时：v\[i\]\[j\]=max\{v\[i-1\]\[j\], v\[i\]+v\[i-1\]\[j-w\[i\]\]\}   ##

该公式描述的是：当准备加入的商品的容量小于等于当前背包的容量的装入的策略。

v\[i-1\]\[j\]：就是上一个单元格的装入的最大值。

v\[i\]：表示当前要装入商品的价值。

v\[i-1\]\[j-w\[i\]\] ：表示在前 i-1 个物品中能够装入容量为 j-w\[i\] 的背包中的最大价值。

# 五 点睛 #

第3步的填表法和第4步的3个公式相互印证，可以结合起来理解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/5c4288247cbf4c138d88d42aadc75ea0.png

动态规划算法

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关动态规划算法

相关大话算法-动态规划算法

相关算法-动态规划

相关【算法】动态规划

相关动态规划算法

相关动态规划算法

相关动态规划算法

相关动态规划算法

相关算法——动态规划

相关动态规划算法