事情的起因是这样子的，10月1日上午，我又一次在出行前收拾东西到最后一刻，并且成功的错过了火车，并且还发现自己背包里仍然忘了几样东西。在改签到晚上的车票之后，我平白在火车站多出了半天思考人生的时间。于是我痛定思痛，又一次萌发了写一个小程序，帮助自己解决出行前打包东西的困难。在我想象中这个程序应该大概是这样的：
- 启动程序，程序会问你一系列的问题，如出行几天，开车为主还是步行为主，飞机行李额多少等，需要用户回答这些问题
- 根据问题的答案，自动生成一份打包清单
我网上搜索了一番，想看看有没有人已经设计过类似的程序，然后我搜到了这个
Knapsack problem algorithms for my real-life carry-on knapsack。这篇文章从生活中的故事出发，循序渐进，并且画了很多生动的图，不过实际上还是介绍了经典的0-1背包问题的解法，对我的“出行清单生成系统”没什么帮助，这个系统以后另说，先看看这个算法。
解决0-1背包问题的关键还是能够有意识的构建如下的状态转移方程：
$$
dp(i, w) = max\{dp(i - 1, w), dp(i - 1, w - w_i) + v_i\}
$$
函数$dp(i, w)$的含义为在可以放前 $i$ 个物品，并限制重量为 $w$ 时，能够获取的最大价值。而这一函数是存在递推关系的，从状态与决策的角度来讲，在处理第 $i$ 个物品的时候，我可以选择 拿 或 不拿，如果 拿 的话，这一步决策带来的价值，等于 上一步决策$(i - 1)$ 在 $w$ 减去我当前物品重量的限制条件 下的最优价值加上本物品的价值，如果 不拿 的话，这一步决策带来的价值，则完全等同于上一步决策 $(i - 1)$ 在 $w$限制条件下 带来的价值。对于这一步决策，只要取最大值就是这一步决策的最优选择。
上面这段话有些绕，而且这里面似乎涉及到一些更理论的知识（如多阶段决策的最优化原理），这里我也是似懂非懂。总之一旦有了这个递推公式，问题就好解了，一般就两种解法：
- 正着解，从上往下解，层层递归，到边界条件上再层层返回结果，值得注意的是，递归方法的一个问题是在不同的递归分支里可能会对同一状态访问多次，造成重复计算，这里一般通过构造一个记忆内存去存储已经计算过的结果。
- 反着解，从边界条件开始（这里是 i = 0，第一个物件），层层往上推。
我看的文章基本上都是讲的第二种解法，通过构造 dp 矩阵（行为物品，列为重量），一层层往上推。然后就是根据递推公式中dp[i,j] 只与上一行(i - 1)中列数小于或等于 j 的元素有关 的特性，使用滚动数组的方法，使空间使用从 dp 矩阵[N * W] 降为 dp 数组 [W]。很多文章中之所以提到要“逆序”更新，也是和刚刚说的特性相关。因为如果正序更新，无法保证后面的 w 更新的时候，所依赖的值，仍旧是上一行的值。
我没怎么刷过题，LeetCode做过的题也基本还处在easy阶段，以前对动态规划也只有耳闻，在火车站又查了很多关于动态规划和背包问题的文章，并且自己动手写了一遍才感觉理解到位。算法的练习放在了
我的Github 法练习仓库/dynamic-programming。其中我自己觉得，似乎还是递归方法更为实用和优雅一些，因为构建dp矩阵，从边界条件开始往上推似乎存在着以下问题：
- 这样做似乎穷尽了决策状态，是否有必要？
- 当背包载重很大或物品质量差距大时，dp矩阵的列会变得非常庞大
还有就是大部分讲背包问题的文章，都只是求解出最优的价值，但没有涉及到如何把最优的打包结果里包含的物品清单输出来。上面的英文文章介绍了dp矩阵的方法中如何输出打包清单。另外我自己在递归的方法中也加入了打包清单的输出，思路有点类似于在通过图搜索进行路径规划的过程中，找到目标点后反向生成路径的方法。
具体的实现过程中，我把每一个 $dp(i, w)$ 视为一个状态节点，在每一次计算得到节点价值的过程中，同时登记当前选择的结果（放/不放），和对应的上一个状态节点是谁。最后，再从 dp(N, W)开始一路倒推，得到整个最优决策树上的每一步选择。
背包问题的变种似乎还有很多，未来遇到时再继续学习。