Lecture 12: More about debugging, knapsack problem, introduction to dynamic programming
本课主要分为三个部分，第一部分介绍了更多在调试时候的注意点；第二部分例举了多个经典优化问题；而第三部分则简要介绍了动态规划。
第一部分提出了许多在调试时应该注意的地方，下面大概有三个重要点，将逐个讲明。
第一个要点是在调试的时候，各位可以注意程序是否出现了以下错误（有些可能非常简单，但仍需要小心谨慎）：
- 自变量顺序错误(Reversed order of arguments)；
- 拼写问题(Spell mistakes)；
- 忘记初始化(Initialization)，注意在使用循环时，初始化应该在循环内部还是外部；
- 对象与值对等(Objects vs. value equality)；
- 注意别名混淆(Aliasing)，例如列表的深复制和浅复制；
- 副作用(Side-effects)，注意程序是否会产生不需要的操作而影响结果。
第二个要点，是在平时写程序并调试的时候，要注意养成时时记录自己错误的习惯，总结成一个个人犯错模型(Personal model of mistakes)。那么在调试的时候，就可以首先查找是否又出现了以前犯过的错误。
第三个要点是在调试的时候，要记录下已经尝试过的修改。不是所有修改都会一次成功，而且有时候调试和修改会花很长时候。因此，这些记录就可以避免重复进行同样的无效修改。另外，由于修改可能会导致程序变得更加糟糕，确保程序可以回转则非常重要。因此，要保存原本的未修改程序和每个修改过的版本（可命名为V1.0, V1.1, V2.1等等）
第二部分则提出了新的问题类型，即最优化问题(Optimization problem)。这些问题都有以下两个显著的特点：
- 包括取最大值或最小值的函数
- 必须满足一定的约束条件
最优化问题包括以下五个非常经典的子类型：
- 最短路径问题(Shortest Path Problem)
- 旅行商人问题(Travelling Saleperson Problem)
- 装箱问题(Bin Packing Problem)
- 调整问题(Sequence Alignment Problem)
- 背包问题(Knapsack Problem)
大多数新的优化问题可以简化为以上五个子类型，而运用这些已知问题的解法可以解决新的问题。
本课重点讲述的是第五种题型，即背包问题。背包问题又分为两种类型，一是连续背包问题，二是0/1背包问题。
背包问题类型1：连续背包问题
例：假设一个贼闯入一户人家，他有一个背包可以装10kg的东西。屋里有以下值钱的东西：
- 4kg金沙
- 3kg银沙
- 10kg葡萄干
那么我们就来系统化一下这类问题：
① 创建一个函数，要求这个函数的最大值或最小值。在这个例子中，就是求背包里面装的东西的最大价值。我们就可以由函数：f = 金沙的价值 x 金沙的重量 + 银沙的价值 x 银沙的重量 + 葡萄干的价值 + 葡萄干的重量。求这个函数f的最大值。
② 考虑约束条件。在这个例子中，金沙，银沙和葡萄干的重量总和 <= 10kg
这个问题的解法非常简单：我们先取4kg金沙，3kg银沙，再取3kg葡萄干。这就是一个简单的贪心算法(Greedy algorithm)，即每一步都是最优解的算法。
然而局部最优策略并不代表全局最优策略，我们可以另一种背包问题，即0/1背包问题。
背包问题类型2:0/1背包问题
（基本上这是不连续背包问题）
例：假设这个小偷的背包仍然只能装10kg的东西，但是他闯入的屋主家只有如下物品：
- 一个手表（重1kg，价值10）
- 一个收音机（重3kg，价值5）
- 一个花瓶（重5kg，价值7）
- 一幅油画（重8kg，价值9）
我们也来系统化这个问题：
① 我们有n件物品，但每一次只能选择拿整件物品或者不拿这件物品；
② 每个物品都有重量和价值，我们要找到最优解，即最大值。
那么，我们会有如下两种方法去解决这个问题：
- 贪心算法(Greedy algorithm)
- 穷举法(Brute-force algorithm)
贪心算法前面已经提到过了，在每一步都取最优解，即取价值最高的物品。所以就是拿一个手表，再拿一幅油画，所以总价值为10 + 9 = 19。这样的算法即快速又简单，但并不是最优解。
最优解是什么？其实就是一个手表，一个收音机加一个花瓶，总价值为10 + 5 + 7 = 22。这个用穷举法也可以做，但是非常慢，在这里一共有2^4 = 16种可能性。但当输入值n很大的时候，就有2^n种可能性，当n足够大的时候，比如n=50，穷举法就需要花很长很长的时候去算出最优解。
那么，这时我们为了提高算法效率，就可以运用动态规划。
什么是动态规划？这就是第三部分讲的内容。由于动态规划是下一节课的内容重点，我就会在下一个笔记中详细讲述，并且写出0/1背包问题的两种解法。
总结：介绍最优化问题系列，重点讲述背包问题，非常重要，初学者必看！
学员评论