关于算法:通过01背包问题理解动态规划

「烤冷面讲算法」系列，每周更新：https://scriptrunz.com/zh-cn/…
「一个干货技术社群」：https://scriptrunz.com/zh-cn/…

01 背包问题

假如你是个小偷，背着一个可装 4 磅货色的背包。你可偷盗的商品有如下 3 件:

为了让偷盗的商品价值最高，你该抉择哪些商品?

暴力搜寻

暴力搜寻法会将每种组合都尝试一遍后找到最优解，不言而喻这种算法的工夫复杂度为 O($2^n$)，只有问题扩充到肯定规模，这个算法肯定行不通。

动静布局

动静布局先解决子问题，再逐渐解决大问题。

对于背包问题，你先解决小背包 (子背包) 问题，再逐渐解决原来的问题。

依照这个思维，咱们尝试将背包容量逐渐放大到 4、3、2、1，计算不同容量的背包所能承载的最大价值。进而，咱们能够画进去一个表格，列 代表不同容量的背包，行 代表不同品种物品。

这是一个表格，也是一个行列式，咱们将这个行列式命名为 dp，dp3 的值就是题解。咱们一步步把行列式的值填满，最终行列式被齐全填满后，题解天然上不着天; 下不着地。

填满行列式

第一行是吉他行，这意味着咱们尝试将吉他装入背包，在每一个单元格都须要做一个决定：要不要把吉他放到背包里。第一个单元格示意背包的容量为 1 磅。吉他的分量也是 1 磅，这意味着它能装入背包！因而这个单元格蕴含吉他，价值为 ¥1500。

到了下一个单元格，它示意背包的容量为 2 磅，齐全可能装下吉他！然而咱们只有一把吉他，所以总价值还是 ¥1500。同理，容量为 3、4 磅的背包总价值放弃 ¥1500 不变。

来到第二行，可偷的商品有吉他和音响。

音响重 4 磅，所以第二行的前三个格子只能抉择吉他，价值 ¥1500。到了第 4 个格子，咱们就能够抉择更贵的音响，总价值 ¥3000。

来到第三行，可偷的商品有吉他、音响、笔记本电脑。

笔记本电脑重 3 磅，所以第 3 行的前 2 个格子只能抉择吉他，价值 ¥1500。到了第 3 个格子，咱们就能够抉择更贵的笔记本电脑，总价值 ¥2000。

抉择了笔记本电脑后，咱们还有 1 磅的空间，此时应该抉择什么呢？

dp1 曾经通知了咱们答案：在背包只有 1 磅容量且仅能抉择吉他和音响时，其最大价值为 ¥1500，加上笔记本的 ¥2000 总价值为 ¥3500，超过了上一行的最大价值 ¥3000，刷新了最大价值记录，同时也拿到了最终的题解。

咱们胜利利用动静布局解决了这个问题，咱们合并了两个子问题的解来失去更大问题的解！

状态转移方程

“ 状态转移方程 ” 这个名字听起来很吓人，其实说白了就是用公式来示意咱们下面的策略，写进去公式咱们能力用代码求解具体问题。

总结来说，选物品的策略有两种：

有了这个公式化的策略，写代码还真就是最简略的一步了～

参考：
1.《算法图解》