goo*_*ing 41 language-agnostic algorithm dynamic-programming
我无法弄清楚动态编程的原理,我真的很想要它.DP非常强大,它可以解决这样的问题:
那么,你能给我推荐好的书籍或文章(最好带有真实代码的例子),它可以解释我什么是动态编程？我首先想要简单的例子,然后我会继续前进.
Ian*_*hop 34
动态编程是一种有用的算法类型,可用于通过将硬问题分解为更小的子问题来优化硬问题.通过存储和重用部分解决方案,它可以避免使用贪婪算法的陷阱.有两种动态编程,自下而上和自上而下.
为了使用动态编程可以解决问题,该问题必须具有所谓的最优子结构的特性.这意味着,如果问题被分解为一系列子问题并且找到了每个子问题的最优解,那么通过这些子问题的解决方案将实现所得到的解决方案.使用动态编程无法解决不具有此结构的问题.
自上而下更好地称为记忆.存储过去的计算是为了避免每次重新计算它们.
给定递归函数,说:
fib(n) = 0 if n = 0
1 if n = 1
fib(n - 1) + fib(n - 2) if n >= 2
我们可以从它的数学形式递归地写出这个:
function fib(n)
if(n == 0 || n == 1)
n
else
fib(n-1) + fib(n-2)
现在,任何已经编程了一段时间或者对算法效率了解一两件事的人都会告诉你这是一个糟糕的主意.原因是,在每一步,你必须重新计算fib(i)的值,其中i是2..n-2.
一个更有效的例子是存储这些值,创建一个自上而下的动态编程算法.
m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
if(m[n] does not exist)
m[n] = fib(n-1) + fib(n-2)
通过这样做,我们最多计算一次fib(i).
自下而上使用与自上而下相同的记忆技术.然而,不同之处在于自下而上使用称为重复的比较子问题来优化您的最终结果.
在大多数自下而上的动态编程问题中,您经常尝试最小化或最大化决策.在任何给定点,您都有两个(或更多)选项,您必须确定哪个选项更适合您要解决的问题.但是,这些决定是基于您之前做出的选择.
通过在每个点(每个子问题)做出最佳决策,您可以确保您的整体结果是最优的.
这些问题中最困难的部分是找到解决问题的重复关系.
要支付一堆算法教科书,您打算抢劫一个有n个项目的商店.问题是你的小背包最多只能保持W kg.知道每件物品的重量(w [i])和价值(v [i]),你想要最大化你的赃物的价值,所有这些物品的总重量最多为W.对于每件物品,你必须做出二元选择 - 要么接受,要么离开它.
现在,您需要找到子问题是什么.作为一个非常聪明的小偷,你意识到给定项目的最大值,i,最大权重w,可以表示为m [i,w].另外,m [0,w](最多权重为w的0项)和m [i,0](具有0最大权重的i项)将始终等于0值.
所以,
m[i, w] = 0 if i = 0 or w = 0
随着你的思维全面罩,你注意到如果你已经尽可能多的重量填充你的包,新的项目不能被考虑,除非它的重量小于或等于你的最大重量和目前袋子的重量.您可能想要考虑某个项目的另一种情况是,它的重量小于或等于包中的项目但更多的价值.
m[i, w] = 0 if i = 0 or w = 0
m[i - 1, w] if w[i] > w
max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w
这些是上述的递归关系.一旦你有这些关系,编写算法非常容易(而且简短!).
v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack
m[n, n] = array(int, int)
function knapsack
for w=0..W
m[0, w] = 0
for i=1 to n
m[i, 0] = 0
for w=1..W
if w[i] <= w
if v[i] + m[i-1, w - w[i]] > m[i-1, w]
m[i, w] = v[i] + m[i-1, w - w[i]]
else
m[i, w] = m[i-1, w]
else
m[i, w] = c[i-1, w]
return m[n, n]
幸运的是,动态编程在竞争性编程方面已经成为现实.查看UVAJudge上的动态编程,了解一些实践问题,这些问题将测试您实现和查找动态编程问题重现的能力.
Wil*_*ler 10
简而言之,动态编程是一种通过将复杂问题分解为更简单的步骤来解决复杂问题的方法,即逐步解决问题.
我希望这个链接至少会有所帮助.
见下文
上面的文章中有太多的样本和文章参考.
在学习动态编程之后,您可以通过解决UVA问题来提高您的技能.在UVA的讨论板中列出了一些UVA动态编程问题
此外维基有一个好简单的样本.
编辑: 有关它的书籍算法,您可以使用:
您还应该看看动态编程中的Memoization.