Dynamic Programming

2019-03-04

动态规划的名字起得不好,其内核与规划不同,更像是分解。使用动态规划的思想可以将可以分解的问题更简便的解决,大多数时候这种问题本身的解决方法就是递归,而动态规划更强调子问题的叠加和重复。

背包问题

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

背包问题用来当作动态规划的例子是十分合理的,因为它可以被描述为一个决定性的问题。有一个背包,我们如何能在总重量不超过 W 的前提下,使总价值达到 V。

这样的问题的难点是:每一个物品都有拿或者不拿两种可能,而任何一个物品的状态都要取决于其他的物品,计算性价比对这个问题效果甚为,需要更全局的考虑方式。

递归

递归的做法是可行的,递归时从第一件物品开始,递归两种可能的结果,对于每一次计算都有如下可能。

假设我们分析是不是应该包含物品n:

通过这种方式,我们可以无限的递归下去,每一个没有副作用的子问题都包括三个参数重量W价值K可以用的物品列表,对于这样的问题,可以用动态规划的问题优化递归算法。

动态规划

实际上,对于我们当前的递归解决方案的动态规划化是非常简单的,重点在子方法是否重叠,无副作用,如果是,那么实际上动态规划的要点就是保存每一个子问题的答案,并在重复我的问题出现时直接使用保存的结果。

那么什么样的问题可以使用动态规划解决呢,除了这些模糊的定义之外有没有标准的分界线呢?! 有的!

Go Back

随便看看 :D