热点 观点 数学

让数学来告诉你高考作文的正确写法:行囊到底该怎么备?

antares 发表于  2016-06-07 22:25

“喏,这些东西你都可以带。随便你挑,可得仔细想想啊,前路漫漫,不带今后就没得用啦。”墨镜黑衣男随手指了指脚边的一堆东西,品种繁多色彩各异,在阳光下折射出无数个闪耀的小光点,仿佛正在嘲讽我一筹莫展的样子。“嗯,对了,这也是你们的作文题,要记得好好写,有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)

题图来源:123rf.com.cn正版图片库

热门评论

  • 2016-06-07 23:54 点点海蓝兽

    你得文章写得很好,有理有据,有思想,有深度,但是由于你使用了黑色以外颜色的笔用于答题,严重违反考试规定有重大的作弊嫌疑,故判该卷0分

    [94] 评论
  • 2016-06-08 09:37 zzzhu

    阅卷老师看到第三自然段就看不懂了,从隔壁找来一位数学老师会诊。

    数学老师从头到尾进行了详细的讲解,并认为写的不错,高兴地回去了。

    语文老师心想,其实他直接让我看最后一句就可以了。。。

    [31] 评论
  • 2016-06-08 00:20 西泽.贝叶斯

    就算找到了NPC问题的多项式复杂度算法,如果其时间复杂度是之类的,其计算量也是属于丧心病狂的。(⊙ˍ⊙)

    [6] 评论

显示所有评论

全部评论(40)
  • 1楼
    2016-06-07 22:26 反向延长线.

    太迟了

    来自

    果壳的核
    [1] 评论
  • 2楼
    2016-06-07 23:54 点点海蓝兽

    你得文章写得很好,有理有据,有思想,有深度,但是由于你使用了黑色以外颜色的笔用于答题,严重违反考试规定有重大的作弊嫌疑,故判该卷0分

    [94] 评论
  • 3楼
    2016-06-08 00:20 西泽.贝叶斯

    就算找到了NPC问题的多项式复杂度算法,如果其时间复杂度是之类的,其计算量也是属于丧心病狂的。(⊙ˍ⊙)

    [6] 评论
  • 4楼
    2016-06-08 03:31 smy20011

    第一次上算法课的时候,听说背包问题是npc我都惊了。

    [3] 评论
  • 5楼
    2016-06-08 08:59 大头米少

    从来不担心NPC,事实上乘法表以外的数学问题我从来都不会去考虑

    [2] 评论
  • 6楼
    2016-06-08 09:10 掌心猬

    愣是把语文作文题答成数学题

    [2] 评论
  • 7楼
    2016-06-08 09:37 zzzhu

    阅卷老师看到第三自然段就看不懂了,从隔壁找来一位数学老师会诊。

    数学老师从头到尾进行了详细的讲解,并认为写的不错,高兴地回去了。

    语文老师心想,其实他直接让我看最后一句就可以了。。。

    [31] 评论
  • 8楼
    2016-06-08 10:09 你舅舅 果壳网新媒体编辑

    _(:з」∠)_所以每次出远门收拾东西可以收上半天并不是我的锅

    [0] 评论
  • 9楼
    2016-06-08 10:10 神采洋

    考试都结束了还在答题,违反考试纪律,判0分!

    [3] 评论
  • 10楼
    2016-06-08 11:21 晨光01

    说明文。可得35分。

    [2] 评论
  • 11楼
    2016-06-08 11:30 天降龙虾

    贝爷表示,绳子、刀子,齐活儿。。。。。。

    [3] 评论
  • 12楼
    2016-06-08 11:54 一千三百公里

    阅卷老师看完一脸懵逼:负分。

    [2] 评论
  • 13楼
    2016-06-08 12:41 WangNianyi2001
    引用文章内容:想想那个著名的国际象棋棋盘上放米粒的例子吧

    unsigned long checkerboard(int index){

      return unsigned long(1<<index);

    }

    [0] 评论
  • 14楼
    2016-06-08 12:42 WangNianyi2001
    引用@WangNianyi2001 的话:unsigned long checkerboard(int index){  return unsigned long(1<<index);}

    不是 O(1) 复杂度么(惆怅.jpg)

    [0] 评论
  • 15楼
    2016-06-08 13:25 -泡芙小姐-

    你的文章真的需要专家来会诊了。

    [0] 评论
  • 16楼
    2016-06-08 14:49 孤胆侠猫

    说真的,现在的高考作文一年比一年混蛋了,一点都没有给象牙塔的学子们的那种天马行空的想象空间和独创性,而且政治性越来越强,和公务员考试的文书写作有一拼了

    [5] 评论
  • 17楼
    2016-06-08 15:24 qzuser_38781

    wow 我也山东的也学数学😂

    [0] 评论
  • 18楼
    2016-06-08 16:20 郑州博泰机械_29551

    高考作文题目一年比一年没什么技术含量了呵呵

    [0] 评论
  • 19楼
    2016-06-08 17:24 体重95KG

    不能拿经历过大学甚至工作10年以上的经历来看待作文,我曾有一个女友是教初中语文的,当年我蛋疼制作被她批评的一无是处

    [1] 评论
  • 20楼
    2016-06-08 21:28 双桅船上的渔夫
    引用@体重95KG 的话:不能拿经历过大学甚至工作10年以上的经历来看待作文,我曾有一个女友是教初中语文的,当年我蛋疼制作被她批评的一无是处

    嘻嘻,女友是教师。。。可以制服paly

    [1] 评论
  • 21楼
    2016-06-08 21:50 歪脖子树下

    语文老师看了开头;嗯有道理~结尾嗯不错~中间一大段~蛮多的的~不过这是什么意思!

    [0] 评论
  • 22楼
    2016-06-09 01:02 新月祥
    引用@双桅船上的渔夫 的话:嘻嘻,女友是教师。。。可以制服paly

    教师有制服?

    [0] 评论
  • 23楼
    2016-06-09 04:36 言十辰知

    This War of Mine时晚上出去搜刮的时候一直在想这个问题

    [1] 评论
  • 24楼
    2016-06-09 13:30 郝钟祥

    你得文章写得很好,有理有据,有思想,有深度,但是由于你使用了黑色以外颜色的笔用于答题,严重违反考试规定有重大的作弊嫌疑,故判该卷0分

    [0] 评论
  • 25楼
    2016-06-09 15:32 双桅船上的渔夫
    引用@新月祥 的话:教师有制服?

    有啊。。正规好点的学校有啊。。。乡下130线外的就没了

    [0] 评论
  • 26楼
    2016-06-09 18:26 72十四

    高考党很开心地从首页点进来,结果

    根本不是我的卷嘛摔!

    [1] 评论
  • 27楼
    2016-06-09 21:38 氘化氢
    引用@西泽.贝叶斯 的话:就算找到了NPC问题的多项式复杂度算法,如果其时间复杂度是之类的,其计算量也是属于丧心病狂的。(⊙ˍ⊙)

    只要n大于996,那它还没有2^n大啊

    而且多项式的值应该始终小于2^n啊


    [0] 评论
  • 28楼
    2016-06-09 22:29 双桅船上的渔夫
    引用@新月祥 的话:教师有制服?

    有啊。。正规好点的学校有啊。。。乡下130线外的就没了

    [0] 评论
  • 29楼
    2016-06-09 23:04 西泽.贝叶斯
    引用@羟酸氢 的话:只要n大于996,那它还没有2^n大啊而且多项式的值应该始终小于2^n啊

    小于是小于,但关键是计算时间:

    假设某台超级计算机的计算速度为:

    则需要计算:年。。。。。。

    所以就算是多项式复杂度算法,次数大了也是不行的。

    [0] 评论
  • 30楼
    2016-06-10 00:03 右京样一

    呃……终于有了个讲背包问题的科普文章……

    [0] 评论

显示所有评论

你的评论

登录 发表评论

antares
antares 数学硕士,本格推理爱好者

作者的其他文章

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区