“喏，这些东西你都可以带。随便你挑，可得仔细想想啊，前路漫漫，不带今后就没得用啦。”墨镜黑衣男随手指了指脚边的一堆东西，品种繁多色彩各异，在阳光下折射出无数个闪耀的小光点，仿佛正在嘲讽我一筹莫展的样子。“嗯，对了，这也是你们的作文题，要记得好好写，有60分呢。”
图片来源：央视新闻微博
我苦笑着看了看手中的背包，背包就这么点容量，要想走完剩下的路，非得想个办法装满那些最有用的东西不可，或者换个说法，尽可能的让我这个背包中的东西价值最大化。这是个问题。
身为一个数学学生，问题总是要解决的。首先我需要理清思路，给每个物品定个价值，很快就要用到的东西定个价值1，暂时用不上的物品通常也会永远用不上，那么定价为0，每天都要喝不喝会死的东西例如可乐…定价当然是10，总之先整理一番再说。比较幸运的一点是这个背包看起来采用了高弹性面料，对于面前的这堆小物件，我暂时不用考虑物品的体积问题。然则作为一只长年不锻炼身体的死宅，负重超过一定重量的话即使喝了可乐我还是会死，因此除了物品的价值，我还需要考虑的因素就只是它们的重量了。
还是摆脱这种无意义的叙述，让我们转换问题到一个更为标准的状态好了：给定n种物品和一个弹性背包，物品i的重量是w_i，其价值为v_i，背包的承重上限为C。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大?
坑爹，这不就是困扰了无数数学家与计算机科学家的背包问题么！
背包问题：只是看起来很简单
你可能会认为，这种鸡毛蒜皮问题有什么好费脑筋的，用得着困扰么?
但是如果你换个角度，想想如果某活动赠送了一张1000元超市购物卡，显然购物车里的东西价格总和最好尽可能接近1000，又最好是每样东西都是你最想要的。是不是感觉这个变种背包问题立刻变成了你经常困扰的问题了？推广到投资应用，运货装船，这类问题显然大家都时常遇到，是个非常重要的问题。
你可能会想：就算再重要又怎样，反正我们有电脑嘛，让电脑把每种可能的组合都算一遍，看看最优解不就可以了么。可是当我们有n个物品时，可能的组合就有2^n个，如果n是个稍微大一点的数，比如100，计算机需要计算10^30种可能性，目前常用的电脑计算速度也就每秒能算10^12次数量级次浮点运算， 这样需要10^18秒左右，相当于10^13天，穷其一生，你居然算不出100件东西里能挑哪些来买，这你能忍？
日常买东西也就算了，遇到举棋不定的时候凭着感觉走也不至于损失太大。但是重大商业决策，可就没这么随便了；数学家更是不能忍，毕竟应用数学家的梦想就是开发出一套算法来，不管你这个问题来多少变数，我都能用一致的办法来解决。于是多年来，在这个问题上人们做了很多种研究，解法大致有两条路。
背包问题看似简单，但实际上既重要又复杂。图片来源：wikipedia
第一条路线：动态规划算法
当背包的重量限制不大的时候，是可以通过“动态规划”求解的。动态规划，简单来说，就是把问题分解成不同的子问题分别求解，然后再合并子问题的解得到原问题的解——等等这绕口令哪里简单了啊？算了还是让我来举个例子吧。
假定我的负重限制是10kg，一共有10种物品需要考虑。这时我可以反着来思考，分成两种可能性。
可能性1：最终我的背包里没有可乐。那么问题就变成了：如何把9种物品放进10kg背包中，使得最后结果最好。
可能性2：最终我的背包里是有可乐的。我知道可乐的重量是1kg，那么背包就还剩9kg余量。那么问题就变成了：如何把9种物品放进9kg背包中，使得最后结果最好。
两种可能性里，价值更高的那个，当然就是我要的那个最优解。
但我还是不知道哪一种价值更高啊？没事儿，我们把这两种情况继续分解下去，现在每种情况都按照有没有饼干来区分。这样直到分解到最简单的情况——比如背包负重只剩下1kg，一切都一目了然。这时候再反推回去，逐渐增加物品做递归，直到实际想要的重量限制10kg为止，就能算出最优解了。
用动态规划算法解NP问题的一个简单例子。图片来源：allsyllabus.com
废话这么多，还是数学爽快。只要这一个公式：
f_n(W)=max{f_(n-1)(W)， f_(n-1)(W–w_n)+v_n}
这种算法的缺点是所需要的计算时间复杂度为O(nW)。“时间复杂度”说白了就是一个算法要花多少时间，不过因为算法可以适用于很多问题，我们一般把它表达成问题本身大小的函数——O(nW)的意思就是，它所花的时间，和背包的负重上限W成正比。
当负重上限W很大时，这个算法相对来说就比较慢，因此通常要做一些优化处理。例如，如果我们在最初的子问题中放入了 1kg的可乐，我特别喜欢它因此价值高达50。而在后续中我们放入了饼干，饼干2kg价值只有30，是不是觉得和可乐比起来，饼干就没什么意义啦？那么之后我们就不需要再考虑单独饼干了。但是我们也同时发现，如果同时放入可乐和饼干，我们能用3kg的重量实现80的价值，那么如果西瓜3kg价值10，那么西瓜也不用考虑了。因此可以用舍弃劣质信息量的方法来简化计算，让动态规划的算法更为快一些。
但是仅仅如此也不够，因此人们又开发了另一种思路来解决。
第二条路线：0-1规划
另外一条路得回归到我们刚刚吐槽过的遍历思路，就是根据物品的重量老老实实求各种组合。显然这是个线性的方程，并且变量要么是0（不选这个物品）要么是1（选这个物品），这样就是一个0-1规划。
如我们刚刚所说，这样就有2^n种组合求最优解，在计算机中形成了一个二叉树，需要做的是遍历这棵树的每一个点。显然这样会太麻烦，前面也说了，算起来会超慢的，因此需要想办法剪去这棵树的枝叶，让找到最优解简单一点。
以下是一些常用的思路。如果某种物品中重量大的超过上限，显然包含它的组合都不用考虑了，这显然是个最清晰直观的简化办法。如果先把这些物品取整数的约束取消，即可以塞入0.x个物品，那么就可以利用单位重量的价值最大这个原则求出一个解，再映射到和这个解相近的整数解上，这样可通过不断迭代来得到最后的答案。关于这类优化问题的算法已经是数学系研究生级别的课题了，也就不再多叙述了。
一个NP完全问题；换言之，真的很难的问题
说到这里，你是不是对背包问题的复杂度有了一个全新的认识？到底有多复杂呢？
来看这样一个简化一点，被称作决定性问题的背包问题版本：给定背包，物品集和一个目标价值V，问能否找出一组物品使总价值至少达到目标价值。这个版本的背包问题，是1972年第一批被证明为NP完全（NP-Complete）的二十一个问题之一。
NP完全问题是什么意思呢？
NP问题在生活中其实无处不在：“-我们就想要价值正好15.05美元的前菜。这些论文或许可以帮到你：）”
“-……还有六桌等着点菜。”“-旅行推销员问题！”图片来源：xkcd
首先，如果对一个问题，有人回答了“是”并且给出了一组解，其他人可以简单验证这组解是否成立的话，这种问题叫做NP问题。
其次，我们希望在随着问题本身规模的变大，它的“难度”——或者说，时间复杂度——不要增长得太过分。如果对于规模是n的问题，我要用指数增长的2^n的时间去解决，那这就太费时了，想想那个著名的国际象棋棋盘上放米粒的例子吧。一个理想的要求是，难度只按照多项式来增长，比如对于规模是n的问题，我只要n^2的时间就好。
最后，在NP问题中，有些问题特别的难，以至于如果我们能找到它的多项式解法，那么所有其他NP问题就都有多项式解法了。这类最难的问题就被称为NP完全问题。
而背包问题，就是一个NP完全问题。
NP完全问题中包含了其他很多实用且常见问题，如旅行推销员问题，0-1规划等等，因此NP问题是否能找到多项式复杂度的解法（P＝NP问题）是计算复杂度理论之中最重要的问题之一。美国克雷数学研究所于2000年悬赏过100万美元的奖金呢。
所以现在也不要再抱怨每次出门前收拾行李时老是难以抉择烦死人了，毕竟，我们可是从数学上证明，箱子里该装什么这个问题实在是太难了啦。 （编辑：Stellasun）