点击上方“程序人生”，选择“置顶公众号”

第一时间关注程序猿（媛）身边的故事

记得小时候，央视有一档综艺节目叫做《超市大赢家》，大致内容是：规定在一段时间内以及只有一辆购物车的情况下，每队可以在超市内任意选购，当然每种商品数量有所限制。

在游戏时间结束时，购物车中商品总价格最高的一队获胜，并且可以免费带走购物车内所有商品。

相信很多人在童年时都看过这档节目，当时对我产生了极大的冲击，简直就是我的人生梦想。

但问题也随之而来了，对于那时生活和购物经验都不足的我来说，到底哪些商品既价格高，所占空间又小呢？而且由于对相同商品的数量有着限制，那么势必需要合理分配购物车的空间，才能使价值最大化，但这又该如何操作和计算呢?

童年的我陷入了矛盾，后来我并没有机会去参加这个节目，不过问题却一直留了下来。

我相信，直到现在，对于这个问题或者类似的问题，依然会有很多人无从下手。我也是在接触了算法之后，才回忆起这个童年难题，并用动态规划去解决它。

我觉得，这也是人们即使不以计算机为职业，不过仍有需要学一些编程知识的意义之一吧。

编程亦如创作

那么我们接下来就以编程的思维去解决这个有意思的问题。

假设我们现在有多种商品，数量都是为一。有人可能会觉得，计算机运行速度那么快，那么我们就把所有可能的情况都列举出来，再计算总价进行比较，不就得出答案了吗？

这样真的可行吗？我们来列出一张表格。

假设超市只有40种商品，就已经出现了10240亿个集合数量。如果一个小超市有上百种商品，用现在的个人电脑，应该从你的童年到老年也计算不出结果。

显然这是不合理的，我们可以使用动态规划，动态规划的思想是：

将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后再将子问题的解作为上层问题的条件，直至求出原问题的解。

童年的小刘不知不觉长大了，在他18岁生日之际，他觉得作为成年人，当然需要一些电子产品，爸爸给了他一个空间为4的包，承诺可以为其中的东西付款。小刘调查了商品一下价格，开始筹划怎样才能最大化地坑爹。

动态规划既然是要将大问题分为若干子问题，那么我们是否可以这么考虑：

1. 假如商场只卖手机。
   1.1 包的空间为1
   1.2 包的空间为2
   1.3 包的空间为3
   1.4 包的空间为4

2. 假如商场只卖手机和平板（1的结果可以为2所用）
   2.1 包的空间为1
   2.2 包的空间为2
   2.3 包的空间为3
   2.4 包的空间为4

3. …

这是我们的思路过程。思路过程种，不难发现，这似乎是一张二维的表：

那我们就开始尝试计算吧。

先只看第一行，只有手机可以挑选，在包的空间递增的过程中，会出现以下情况：

现在继续看下一行，此时有手机和平板可供选择，包的空间在递增，此时已经存在第一行的数据可以使用，不必重复计算：

我们不难归纳出算法：

1. 获取上一行同列商品的价格

2. 获取当前行商品的价格+剩余空间可放置价格

3. 对以上两者进行比较，取其大者

这样，我们可以得到，在能够选择的商品种类下，随着包的空间递增，能够获取的最大的价值。那么我们的终极目标，就是右下角的那个格子的值。

现在我们尝试用代码来实现一下，我这里选择的是Python，当然算法的实现和语言本身没有任何关系，哪种最顺手，最便捷即可。

可左右滑动查看

输出：

计算出最后的结果是8000元，由于商品数量比较少，这时候我们可以将这个数据与枚举方法所得的结果进行比较检验，发现是与预期结果一样的，

为了更一般化，可以更改几组测试用例进行多次测试。

需要注意的是，动态规划很强大，但是局限在与：每个子问题都必须是离散的，即相互之间不存在依赖。

童年，电视机是一个世界

童年，曾经有一道复杂的难题摆在我面前，我不会解，等我现在能够解决了，却发现依旧没有能力为我的购物车支付，人世间最痛苦的事莫过于此。

如果上天能够给我一个再来一次的机会，我会对小时候的我说：早点学计算机。

- The End -

「若你有原创文章想与大家分享，欢迎投稿。」

加编辑微信ID，备注#投稿#：

程序 丨 druidlost  

小七 丨 duoshangshuang

2018 AI开发者大会重磅嘉宾及深度议题已火热出炉，扫码抢“鲜”看。国庆特惠，票价立享 5 折优惠！

往期精彩内容