TBWORKs Full-stack Labour/全栈民工

从0-1背包到无限制背包,到背包变种

2014-04-01
Tommy.Tesla

问题背景

0-1背包

给定n个物品,考虑他们的重量 和 价值,分别为   w[0], w[1], w[2], w[3] … w[n-1] 和  v[0], v[1], v[2], v[3], v[4] … v[n-1]。 现在有一个载重量为 W 的背包,求这个背包能放入的物品组合的最大价值。(每个物品只有一件)。

物品数量无限制背包

给定n种物品,考虑各个种类的物品单件的 重量 和 价值,分别为   w[0], w[1], w[2], w[3] … w[n-1] 和  v[0], v[1], v[2], v[3], v[4] … v[n-1]。 现在有一个载重量为 W 的背包,求这个背包能放入的物品组合的最大价值。(每种物品数量无限,可以任意取)。

0-1背包问题解法

考虑0-1背包问题,先来把最容易想到的动态规划算法写出来。我们设d[i][j] 表示 前 i 个物品在背包容量为j下的最优价值。这时候,对于第 i个物品 (物品下标从 0开始),d[i+1][j]表示前i+1个物品(即第0号、第1号、……第i号) 在背包容量为j 下的最优价值。

NOTE: 前i+1个物品分别为 第0号、1号、……i个物品。在动态规划算法实现过程中,正确使用数组下标,可以节省很多控制代码。本算法中,大致规则为:如果使用正向推演(从第一个开始往后),那么需要把第0行数据初始化为0,即第0行代表前0个对象,价值显然为0;第一行代表前一个物品(即第0号物品)。如果使用逆向推演(从最后一个开始往前),那么需要把最后一行(第n行)数据初始化为0,即第0行代后(n-0=n)个物品,第n行代表后(n-n=0)个物品(不存在),价值显然也为0。这样下面的 i+1,w[i] 就好理解了

我们已经知道了 前 i 个物品(即第0号、第1号、……第i-1号)的最优解,为 d[i][j], 0<= j <= W  考虑第i号物品 潜在选择方案有两种: (1) 如果不放入这号物品,那么显然 d[i+1][j] = d[i][j] ; (2) 如果放入这号物品,那么 d[i+1][j] = d[i][j-w[i]]+v[i]; 那么,什么情况下要放入这号物品呢?什么时候不放呢? 首先要看看w[i]是否比j大,如果比j大,那么背包放不下,就不用考虑了,肯定不放了,d[i+1][j] = d[i][j]。 如果w[i] <= j,那么背包能放下,就需要考虑放还是不放了,先放进去看看价值 d[i][j-w[i]]+v[i]的大小,再看看不放进去的大小d[i][j],然后取大的那个作为最优值即可。 递推关系式如下:

d[i+1][j]=d[i][j]                               w[i]>j
d[i+1][j]=max(d[i][j], d[i][j-w[i]]+v[i]  )     w[i]≤j

代码如下:

int w[n];//重量
int v[n];//价值
int d[n+1][W+1];//memset初始化为0
for(int i=0;i<n;i++)
 for(int j=0;j<=W;j++)
   if(w[i]>j)
      d[i+1][j]= d[i][j];
   else
      d[i+1][j] = max(d[i][j],d[i][j-w[i]]+v[i]);
cout<< d[n][W]; //前n个物品在背包重量为W下的最大价值

数量无限制背包问题

物品数量无限制背包: 给定n种物品,考虑各个种类的物品单件的 重量 和 价值,分别为   w[0], w[1], w[2], w[3] … w[n-1] 和  v[0], v[1], v[2], v[3], v[4] … v[n-1]。 现在有一个载重量为 W 的背包,求这个背包能放入的物品组合的最大价值。(每种物品数量无限,可以任意取)。 其实最为简单的一种解法是:把每种物品的个数确认下来,然后当作不同物品,这样就转换成了0-1背包问题。 比如 A B C三类物品,背包分别最多放3个A物品,2个B物品,或 2个C物品。 那么问题变成: a1, a2, a3, b1, b2, c1, c2 共7个物品,只能取一次。 这样算法的复杂度为 nWk, k和W是线性关系 k= ?*W,所以 复杂度为 nWW, 复杂度有点高。 看下面这种思考方式: 若在 d[i+1][j] 取最优时,背包含有2个第i号物品,那么在 d[i+1][j-w[i]] 取最优时,背包必然含有1个第i号物品。 证明:反正法 如果在d[i+1][j-w[i]]取得最优时,背包不含有第i号物品,且在d[i+1][j]取得最优值时,背包含有两个第i号物品。 那么当d[i+1][j]取得最优时,扣掉一个第i号物品,d’[i+1][j-w[i]] 将不是最优的,因为里面还有第i号物品,那么这时候我们用最优的 d[i+1][j-w[i]] (不含有第i号物品)来加上一个第i号物品,应当获得的d’[i+1][j]更大,这和d[i+1][j]已经是最优值相矛盾。 有了这种思维方式,可以知道,在考虑同一种物品时,d[i+1][j] = max (d[i+1][j-w[i]] +v[i], d[i][j]); 这句话的意思是,直观的方案有两种: (1) 一个第i号物品都不放,也就是 d[i+1][j]=d[i][j]; (2) 装入k个第i号物品。若,选择 装入k个第i号物品 时 d[i+1][j] 最优,那么在d[i+1][j-w[i]]最优时,背包肯定含有k-1个第i号物品(上面证明过)。所以 d[i+1][j]=d[i+1][j-w[i]] +v[i];   其实还有一种可行方案: (3) 装入1个第i号物品。d[i+1][j] = d[i][j-w[i]] +v[i];这样一来, d[i+1][j] = max (d[i+1][j-w[i]] +v[i], d[i][j-w[i]] +v[i],d[i][j]);其实,d[i+1][j-w[i]]必然是大于或者等于 d[i][j-w[i]]的,所以才简化为: d[i+1][j] = max (d[i+1][j-w[i]] +v[i], d[i][j]); 这种递推方法要求,d[i+1][j-w[i]] 在d[i+1][j] 前先被更新,所以,j的循环递增方向应该是从小->大。 这时候,我们可以写出无限制背包问题的算法代码。

int w[n];//重量
int v[n];//价值
int d[n+1][W+1];//memset初始化为0
for(int i=0;i<n;i++)
 for(int j=0;j<=W;j++)
      if(j<w[i])
	  d[i+1][j] = d[i][j];
      else
          d[i+1][j] = max(d[i][j],d[i+1][j-w[i]]+v[i]);
cout<< d[n][W]; //前n种物品在背包重量为W下的最大价值
	  d[i+1][j] = d[i][j];
      else
          d[i+1][j] = max(d[i][j],d[i+1][j-w[i]]+v[i]);
cout<< d[n][W]; //前n种物品在背包重量为W下的最大价值

要解决背包问题以及其他变种背包问题,通用策略为: (1) 找出最佳递推方程。 (2) 敲写代码,完成算法。 其他背包变种: 在0-1背包中,加入限制条件:总选择的物品数目为 M。(提示:算法复杂度 nWM) 在无限制背包中,加入限制条件:总选择的物品数目为M。(提示:算法复杂度 nWM)


上一篇 项目经历

评论留言

目 录