背包问题

假设你是一个小偷，背着一个可装4磅东西的背包。
你可盗窃的商品有如下3件。
image.png
为了盗窃价值达到最高，你该怎么选？

简单算法

尝试所有组合
3个商品时你需要计算8种不同的集合。每增加一个商品，集合数都会翻倍。（大O表达式 O(2)）

面对NP问题时，我们之前了解到可以使用近似解，但是如何找到最优解呢？
答案就是使用动态规划。

定义

动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题。
网格：
image.png
需要画一个网格 y轴表示商品，x轴表示重量。
格子内写价格。
逐个填入某个重量下可以放下的商品价格。格子内的价格需要累计，并且在填入时判断是否有更优的选项。
最终结论：
image.png

值得注意的几点

再加一件商品将如何？
行的排列顺序发生变化对结果不产生影响
也可以逐列填充网格
添加一个更小的商品，需要把重量的粒度减小
可以偷商品的一部分吗？动态规则不能处理这类问题。
动态规则可以算出最大最小的值，但不能处理依赖。
动态规则最多只能合并两个子背包，但子背包可以有子背包。
最优解可能导致背包没装满

动态规划的特点

可在给定约束条件下找到最优解
在问题可分解为彼此独立的问题且离散的子问题
每种动态规划都涉及网格
单元格中的值就是你要优化的值
每个单元格都是子问题，你应该考虑如何将问题分成子问题，有助于找到网格的坐标轴

绘制表格

要知道单元格的值是什么
如何将这个问题划分为子问题
网格的坐标轴是什么

最长公共子串

你需要找到两个单词的最长公共子串hish和fish （实际应用：输入法单词补全）
原始表格
image.png
填充后
image.png
注意：最长公共子串问题答案不在最后一个单元格中。
image.png

最长公共子序列

假设我不小心输入了fosh，我原本想输入的是fish还是fort呢
用最长公共子序列解决
结果
image.png
填写单元格时的公式
1.如果两个字母不同，就选择上方和左方邻居中较大的那个
2.如果两个字母相同，就将当前单元格的值设置为左上方单元格的值加一。
image.png

使用场景
生物学家根据最长公共序列来确定DNA链的相似性，进而判断两种动物或疾病有多相似
git diff 指出了两个文件的差异，也是用动态规划实现的
编辑距离指出了两个字符串的相似程度，也是动态规划实现的，可以应用到拼接检查到判断用户上传资料是否盗版
断字功能 ，也是使用动态规划