【动态规划】 01背包问题

动态规划的一个经典问题：背包:

 

01背包

 

描述：有N件物品和一个容量W的背包,(每件物品只有一件可选)，第i件物品重量为W[i]，价值是P[i]。求解将哪些物品装入背包可以使背包容纳的价值总和最大（在背包容量允许的情况下）。

 

特点：对于每件物品，要么放入背包，要么不放入背包

 

初始化：

1、  当背包容量为0时，则不论放入前面多少个物品产生的价值都为0

所以有：f[0…n][0] = 0

2、  当不放入物品时无论多大的背包产生的价值都为0

所以有： f[0][0…W] = 0

 

递推关系式：

用f[i][w]表示前i种物品放入容量为w的背包中能产生的最大价值。那么可以得到递推式：

 

       if ( w > wi)

              f[i][w] = max{ f[i-1][w] ,  f[ i-1][ w-wi ] + pi }

       else

              f[i][w] = f[i-1][w]

 

如果当前背包容量大于当前的物品的大小，那么对于当前物品就有放入和不放入两种选择

1、  不放入 f[i][w] = f[i-1][w] 。不放入则前i个物品得到的最大价值和前i-1个物品放入w容量的值相同

2、  放入 f[i][j] = f[i-1][w-wi] +pi。 由于当前物品i放入，占用了wi的空间，所以前i-1个物品能放入的空间只有w-wi，所以当前得到的价值是前i-1个物品放入w-wi容量的背包的到的最大价值加上当前物品的价值pi

 

f[i][w] = f[i-1][w]：如果当前背包容量小于当前物品的大小，则当前物品不能放入背包，当前的最大价值为i-1个物品放入w容量背包的最大价值

 

 

完全背包

 

描述：与01背包不同的是完全背包对于各种物品可以取0到无穷次，而01背包中的前提是每种物品只可以取一次。

 

优化：对于物品i和j，如果wi   pj 则物品j可以直接从可选物品中去掉，因为在任何情况下都可以选择物美价廉的物品i代替j。

 

解法1： 对于第i件物品， 可以放入背包的最多次数是 (W/wi) ， W是背包的总容量，所有可以将物品i转换成为（W/wi）件大小和价值相同的物品，这样就和01背包问题相同了，只需将01背包最内层循环再加一个循环就可以了

 

解法2： 对于第i件物品，可以构造出新的物品，新物品大小为 wi*(2^k) 价值为wi*（2^k） （k=0…），前提条件是wi*(2^k)<=W 。这样就相对解法1做出了一定的优化。