本文参加百家号#科学了不起#系列征文赛。
假设你是一个小偷，在博物馆展览会上抢劫珠宝和稀有宝石。你是新来的，所以你只带了一个背包。你的目标应该是带着最有价值的东西离开，而不让你的包超载，直到它断裂或变得太重拿不动。你如何在这些物品中做出选择来最大化你的战利品？你可以列出所有的工件和它们的重量来手工计算出答案。但是对象越多，这种计算对个人或计算机来说就越麻烦。
这个虚构的难题，即“背包问题”，属于一类以挑战计算极限而闻名的数学问题。背包问题不仅仅是一个思维实验。澳大利亚墨尔本大学教授卡斯滕穆拉维斯基表示：“我们在生活中面临许多问题，无论是商业、金融，包括物流、集装箱船装载、飞机装载——这些都是背包问题。”“从实用的角度来看，背包问题在日常生活中无处不在。”
研究人员曾经利用这个问题的复杂性来创建计算机安全系统，但现在这些系统可以被破解，因为这个问题已经得到了很好的研究。今天，随着有能力打破数字通信锁的技术即将出现，背包问题可能会激发出为这场革命的新方法。
AllorNothing
背包问题属于一类“NP”问题，即“不确定多项式时间”。这个名称是指这些问题如何迫使计算机经过许多步骤才能得到解决方案，而这些步骤的数量会根据输入的大小急剧增加——例如，在装入特定的背包时要选择的物品的库存。根据定义，NP问题也有易于验证的解决方案。
理论家们开始