DP动态规划算法理解

短命女 2022-05-17 00:17 334阅读 0赞

#                                       DP动态规划算法理解 #

学习了DP动态规划算法，对动态规划也有了一点理解，动态规划是将原来的一个大问题分解为一个简单的子问题，找到子问题的答案，再通过子问题与原问题的关系找出原问题的答案。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题重新计算。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

本次练习中最多的问题就是背包问题，背包问题分为01背包、完全背包和多重背包，01背包是n件物品每个物品只能装一次，使得m的容积所装的价值最大，可以开一维的dp数组也可以开二维的dp数组，二维dp数组dp\[i\]\[j\]存储的是i件物品当背包所剩空间为j时所能装的最大价值利用双重循环更新dp数组的最大值当j<v\[i\]，背包空间小于第i件物品的体积时，dp\[i\]\[j\]=dp\[i-1\]\[j\]；当j>=v\[j\]时dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i-1\]\[j-v\[i\]\]+w\[i\])；而一维数组是将背包空间倒着查找，外层循环为1~n件物品背包空间倒着查到v\[i\]就进行下一轮循环，dp\[j\]=max(dp\[j\],dp\[j-v\[i\]\]+w\[i\])；一维数组dp存储的是当背包空间剩余j时共n件能装的最大价值。相对于二维数组一维数组更加节省空间。[https://blog.csdn.net/kongsanjin/article/details/81359197][https_blog.csdn.net_kongsanjin_article_details_81359197]

完全背包是有n种物品每种物品都可以无限次的装，还是使得容积为m的背包所装的价值最大，完全背包的实现只要将背包的空间进行正着查找就行了，这样就会当装上物品能使背包的价值更大，就会再次装上此物品，使得背包价值更大。（这是一个完全背包只不过控制条件多了）[https://blog.csdn.net/kongsanjin/article/details/81359573][https_blog.csdn.net_kongsanjin_article_details_81359573]

而多重背包就是有n种物品，给出每种物品的体积，价值和数量，如何让背包里装入的物品具有最大的价值总和？其实和01背包是一样的，只不过是每种物品的数量可能不同，也可以看成01背包来做，把所有的物品总数求出来，按01背包二维数组来做，也可以用一维数组外层两个循环，控制种类和数量。[https://blog.csdn.net/kongsanjin/article/details/81358717][https_blog.csdn.net_kongsanjin_article_details_81358717]

我认为动态规划的问题还是要具体情况具体分析了，一般都是要先将原问题分解成子问题，再确定状态，确定初始状态和边界的值，找出状态转移方程。

[https_blog.csdn.net_kongsanjin_article_details_81359197]: https://blog.csdn.net/kongsanjin/article/details/81359197
[https_blog.csdn.net_kongsanjin_article_details_81359573]: https://blog.csdn.net/kongsanjin/article/details/81359573
[https_blog.csdn.net_kongsanjin_article_details_81358717]: https://blog.csdn.net/kongsanjin/article/details/81358717