贪心、动态规划与人生

本篇文章献给我最爱的她,谨此以纪念这个美好而特殊的日子。

贪心算法与动态规划算法都是最优化问题常见的基本算法。某些问题上,贪心与动态规划具有一定的比较研究价值。所处理的问题都是有在局部或者全局存在最优目标的问题。这篇文章我们不做具体的理论分析,只在高观点上谈一谈思想。

看起来计算机算法与我们的日常生活搭不上关系,其实仔细研究也能参悟到些许的人生智慧。

0-1背包问题

有一个淘金者在金矿寻宝时,发现有n个金块,第i件金块价值vi元,重wi磅,此处vi与wi都是整数。他希望带走的金块越值钱越好,但他的背包中至多只能装下W磅的东西,W为一整数。应该带走哪几块金子?这个问题之所以称为0-1背包,是因为每个金块或被带走;或被留下;淘金者不能只带走某个金块的一部分或带走同一金块两次。

首先,这个问题我们可以尝试全部的可能,每件物品要么选,要么不选,所以总共有2^n种组合,比较全部组合后,我们总能找到最优解。但是当n比较大的时候,代价无法承受,所以这里我们用点高效的办法。

贪心解法

简单的说,贪心算法可以看作是每个阶段都做最优的选择以局部最优达到全局最优。所以这种想法的实践很简单,就是每一次做出选择时,我都要挑选最好的。这里的怎么最好怎么去定义呢?

id 1 2 3
value 60 100 120
weight 10 20 30
v/w 6 5 4

现假设我们拥有一个容量为50kg的背包

  • 按照贪心的策略,第一次选择我们先看性价比最高的那个物品,也就是对应1号,价值60,重量10kg的。第二阶段,背包容量剩余40kg,在20kg和30kg的物品中,我们只能选择一个,这种用性价比贪心地作为每次决策衡量标准的办法,做出的最好选择是价值160
  • 然而,事实上,我们不选择第一个,而是选看起来性价比不那么高的2和3,达到最高的总价值:220

虽然我只提供了三个例子,但是注意,我们不能穷举所有可能,因为在数据量极大的时候其代价无法承受。贪心解法在0-1背包问题中最大的弊病就是无法保证背包本身被充分填充,而剩余空出来的空间稀释了原本的性价比。

动态规划解法

定义

f[i][w] : 表示前i件物品放入容量为w的背包中可以获得的最大价值,f[2][30]就是前面2个商品放入重量为30的背包中可以得到的最大价值。
现给出状态转移方程: f[i][w] = max{f[i-1][w], f[i-1][w - weight[i]] + value[i]}

解释

状态转移方程的意义:f[i][w]可以获得的最大价值就是:

  1. f[i-1][w],即不包括第i个物品,总容量为w时的价值。
  2. f[i-1][w - weight[i]] + value[i],包括第i个物品。如果包括第i个物品,那么前(i-1)个物品只能至多占用(w - weight[i])的容量,并且我们需要加上第i个物品的价值。
演示

依旧使用上述例子,f[3][50]就是我们的目标,定义f[x][0] = 0,x为大于0的整数。

  1. f[3][50] = max {f[2][50], f[2][50 - 30] + 120}
  2. 计算f[2][50]与f[2][20] (50-30=20),先计算f[2][50] = max{f[1][50], f[1][50 - 20] + 100}
  3. 计算f[1][50] = 60,f[1][30] = 60
  4. 接着计算f[2][20] = max{f[1][20], f[1][0] + 100}
  5. 计算f[1][20] = 60
  6. 现在我们往回迭代,f[2][20] = max{60, 0 + 100} = 100
  7. f[2][50] = max{60, 60 + 100} = 160
  8. f[3][50] = max{160, 100 + 120} = 220

看,我们找到了正确的结果。动态规划(DP)做出的选择就是2,3这两个物品。相比较于贪心,DP并没有保证任意阶段最优,而是牺牲某一个或多个局部阶段达到全局最优。

总结

人生当中何尝不是如此呢?每一次抉择选择看上去最好的,最终能否达到一开始所设想的结果呢?假设我们面临了一次选择,可能共有10种可能,但我们只看得到3种。也就是说,每一次的选择已经未必是最优了,而这不断的选择的过程组成了我们的人生。人的一生当中也一定存在被迫的不得意的选择。回过头看,如果你对当下满意,达到了你所定义的那个最优,就是因为某一阶段的不尽如人意之后的巨大的改变导向了所能给予的整个人生或者小阶段目标的美好结果。

而且我们在真正了解自我之前,所定义的理想人生未必和了解自我后一致。也就是说我们在了解自我前所做的选择可能会使自己逐渐远离真正的自我,最终导向自我的迷失。这也就印证了往往我们要得到全局的最优,或许必须在某个局部做出取舍,不得不装下不算太好的选择。而这一切的一切,都是为了让我们最终走向幸福~