title: 动态规划
categories:

• Algorithms
  tags:
• 动态规划
  abbrlink: 2819424305
  date: 2019-11-12 16:17:29

动态规划

基本定义

• 通过把原问题分解为想对简单的子问题的方式求解复杂问题的方法。

• 适用于：

  • 重叠子问题
    • 在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。
  • 最优子结构
    • 最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。

基本思想

若要解决一个给定的问题，则要解其不同部分的问题，再根据子问题的解求出原问题的解

实例

背包问题

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

我们有 n 种物品，物品 j 的重量为wj，价格为pj。
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。

可以用公式表示为：

最大值 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XofSVhPI-1573567885471)(https://wikimedia.org/api/rest_v1/media/math/render/svg/5afdaef4d007e84cf2371df93cf7bdc891ddc1d4)]

受限于 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jUVGw23l-1573567885472)(https://wikimedia.org/api/rest_v1/media/math/render/svg/4302b7359d0374df8424621a29a8a4f41f8d017c)]

如果限定物品j最多只能选择bj个，则问题称为有界背包问题。
可以用公式表示为：

最大值 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Bejonopu-1573567885473)(https://wikimedia.org/api/rest_v1/media/math/render/svg/5afdaef4d007e84cf2371df93cf7bdc891ddc1d4)]

受限于 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FRRnOfoz-1573567885473)(https://wikimedia.org/api/rest_v1/media/math/render/svg/dcc77ece1703114b78feaf35faa0e99de9b4b34a)]

如果不限定每种物品的数量，则问题称为无界背包问题。
各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。