假设你是个小偷，背着一个可装4磅东西的背包。你可盗窃的商品有如下3件。可偷商品
为了让盗窃的商品价值最高，你该选择哪些商品？
简单算法
最简单的算法如下：尝试各种可能的商品组合，并找出价值最高的组合。
这样可行，但速度非常慢。在有3件商品的情况下，你需要计算8个不同的集合；有4件商品时，你需要计算16个集合。每增加一件商品，需要计算的集合数都将翻倍！这种算法的运行时间为O (2 n )，真的是慢如蜗牛。
动态规划
动态规划先解决子问题，再逐步解决大问题。
对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。
1
2
3
最终解
假设你发现还有第四件商品可偷——一个iPhone！
1
2
3
假设你还可以偷一条项链，它重0.5磅，价值1000美元。前面的网格都假设所有商品的重量为整数，但现在你决定把项链给偷了，因此余下的容量为3.5磅。在3.5磅的容量中，可装入的商品的最大价值是多少呢？不知道！因为你只计算了容量为1磅、2磅、3磅和4磅的背包可装下的商品的最大价值。现在，你需要知道容量为3.5磅的背包可装下的商品的最大价值。由于项链的加入，你需要考虑的
粒度更细，因此必须调整网格。
使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。
动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用 。
动态规划都有哪些实际应用呢？
生物学家根据最长公共序列来确定DNA链的相似性，进而判断两种动物或疾病有多相似。
最长公共序列还被用来寻找多发性硬化症治疗方案。
你使用过诸如git diff 等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。
前面讨论了字符串的相似程度。编辑距离 （levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。
编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！
网友评论