彻底搞懂动态规划解01背包问题

06 November 2013

引子

在大学的时候,有数据结构与算法的课程,课程中也会讲到01背包问题,那时只是一知半解,想当然认为是这样,但是要真正理一下里的流程,又无从下手 ,于是痛定思痛,重新去google了一番,终于有所领悟。

问题还原

一个背包,承重为W。现在有一堆不同的石头,每块石头的重量和价值都不一定相同,也就是说不是确定的,问题是如何装,才能确保包里面的石头最有价值。

问题的描述可能还有其它版本,有些版本是用体积的。比如背包的体积是V,每块石头的体积和价值都不一定相同。我这里暂用重量吧,都是一个意思。

思考

如果这是一个无界背包问题,就是指,石头是可以切割的,那我们可以用贪心算法来做,算出每块石头的单位重量价值,优先把价值高的石头放进去,如果超重的话, 就把这个超重的石头给切了刚好放满就能解决问题了。

01背包问题和无界背包有点不同,不同点在于,石头不能切割,对于一块石头而言,只能有2种选择,放进去与不放进去,莎士比亚说过:“be or not to be that is a question”,用来形容这个问题很形象。

我们先抽象一下问题的解,设f(n,w)为01背包问题的解,n为前n个石头,w为背包最大承重,这里并不是说就肯定把n个石头都放进去,显然和问题相悖,n指的是有n 个石头可选择。f(n,w)也就是在有n个石头可选择的情况下,放入承重为w的背包中,背包内有最大价值的最优解。

分析

我们来分解下面几种情况

  1. 当w为0时,即不管有几个石头,这个包什么都不能装,显然f(n,0)=0;
  2. 当n为0时,即不管这个包能承重多少,没什么物品可选,显然f(0,w)=0;
  3. 当w,n都不为0时,我们可以看看n-1的情况;

当然,不要忘记一个约束条件,就是任何时候都不要过载哦。


tags:    01背包    动态规划    算法   
回到首页