【整理行李高中作文】高考作文：行囊到底该怎么准备？数学老师说这道题我得做！

(文/antares)“现在，这些东西都可以带走。随便挑也要仔细想想，前路漫漫，没有前路是没有用的。(莎士比亚。)穿着墨镜黑色衣服的男人指着脚边的一堆东西，用各种颜色在阳光下映出无数闪亮的小颜色，好像在嘲弄我。(威廉莎士比亚，哈姆雷特，)“嗯，是的，这也是你们的作文题。要好好写。是60分。”

图片来源：中央电视台新闻微博

我苦笑着看了看手上的背包。背包这么大。要想结束剩下的路，必须想办法填满最有用的东西。或者换句话说，要尽可能最大限度地提高这个背包里东西的价值。(威廉莎士比亚。哈姆雷特。)这是个问题。

作为数学学生，问题总是要解决的。首先，我要整理思想，给每件东西定价值，给即将使用的东西定价值1。暂时不能使用的东西通常也永远不能使用。那么定价为0，每天都要喝不喝就能死的东西。例如可乐.价格当然是10。不管怎样，整理一下再看。幸运的是，这个背包似乎采用了高弹力面料。对于前面的这些小东西，暂时不用考虑东西的体积。大卫亚设，Northern Exposure(美国电视剧)，幸运名言)那么，作为一个长期不锻炼身体的死宅，如果重量超过一定量，喝可乐我也会死，所以除了东西的价值外，我要考虑的因素只是它们的重量。(大卫亚设)。

或者让我们摆脱这种毫无意义的叙述，把问题转换成更标准的状态。给定的N种物品和弹性背包，物品I的重量是w_i，其价值是v_i，背包的来历上限是C。背包中装载的物品该如何选择(物品不能分割)，背包中装载的物品的总价值应该最大化吗？

坑爹，这不是困扰无数数学家和计算机科学家的背包问题吗！

[背包问题：看起来很简单]

你可能认为这种微不足道的问题有什么苦恼，但有必要麻烦吗？

但是如果改变角度，在某个活动中赠送1000韩元的超市购物卡，购物车里的东西的价格总和最好接近1000，一切都是你最想要的。(大卫亚设，Northern Exposure(美国电视)，)变种背包问题似乎正是你经常苦恼的问题？投资应用，货物装运，这些问题显然是大家经常遇到的非常重要的问题。

不管多么重要，反正我们有电脑嘛。让电脑把所有可能的组合都算一遍不就行了吗。看最优解不就行了吗。(大卫亚设，Northern Exposure)但是当我们有n件东西的时候，可能的组合是2 n件。如果n是稍微大一点的数字，比如100，计算机要计算10 30种可能性。目前常用的计算机计算速度也可以计算每秒10 12次数量级浮点运算。10需要18秒左右，相当于10

每天买东西也就算了，围棋不定的时候凭感觉走也不至于吃大亏。(威廉莎士比亚，《哈姆雷特》)但是重要的商业决定并不那么随便。数学家更是受不了。毕竟应用数学家的梦想是开发算法。不管你这个问题来了多少变数，我都能用一贯的方法解决。(威廉莎士比亚、哈姆雷特、数学家、数学家、数学家、数学家、数学家、数学家)所以多年来，人们对这个问题进行了各种研究，解法大体上有两种方法。

背包问题看起来很简单，但实际上很重要，也很复杂。图片来源：维基百科

[第一条路径：动态编程算法]

背包重量限制不大的时候，可以通过“动态计划”解决。动态规划，简而言之，就是把问题分解成不同的子问题分别解决，结合子问题的解决，得到原来问题的解决——等。这个绕口令哪里简单？算了，我给你举个例子吧。

假设我的负荷限制是10公斤，一共要考虑10种东西。这时候我可以反过来想，分为两种可能性。

可能性1:毕竟我的背包里没有可乐。那么问题是：如何把9种东西放在10公斤背包里，以最好地制作最终结果？

可能性2:毕竟我背包里有可乐。我知道可乐重1公斤。那么背包里还有9公斤的余量。那么问题是：怎么把9种东西放在9公斤背包里，最终结果最好。

在两种可能性中，价值更高的当然是我想要的那个最优解。

但是我还是不知道什么价值更高。没关系，我们一直在分解这两种情况，现在每种情况都是根据有没有饼干来区分的。直到分解成这样最简单的情况，以——为例，背包的重量只剩下1公斤，一切尽收眼底。这个时候再往后推，直到实际想要的重量限制在10公斤为止，递归地增加东西，就可以计算出最佳解法。(莎士比亚)。

这是一个使用动态编程算法解决NP问题的简单例子。照片来源：all

废话这么多，数学还是很爽的。只要有这个公式：

F _ n (w)=最大值{f _ (n-1) (w)，f _(n-1)(ww _ 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）

来源：果壳

本文版权属于果壳网（guokr.com），禁止转载。

如有需要，请联系sns@guokr.com