完全背包问题

短命女 2022-07-12 06:37 199阅读 0赞

# 1. 问题描述 #

有 N 种物品, 物品 i 的重量为 wi, 价格为 vi, 背包所能承受的最大重量为 W。

其中,

N,W,wi,vi≥0

若每种物品仅有一件, 即每种物品的装入状态为 xi, xi∈\{ 0,1\}, 则称该问题为**0-1背包问题**。

若每种物品可取任意件, 则称该问题为**完全背包问题**。

# 2. 转化为0-1背包问题 #

完全背包问题是对0-1背包问题的拓展, 它取消了对每种物品拾取数量的限制。

一种朴素的思想就是将完全背包问题转化为0-1背包问题, 依然采用动态规划的思想进行求解。

*  设 xi 为物品 i 的数量, 则一定有 xi∈\[0,⌊Wwi⌋\], 即可看成物品总数为 ∑Ni=1⌊Wwi⌋ 的0-1背包问题。
 *  状态转移方程为,
    
    dp(1,j)=⌊jw1⌋v1
    
      
    
    
    dp(i,j)=max(dp(i−1,j−kwi)\+kvi)    0≤kwi≤j
 *  0-1背包问题需要填充 N∗(W\+1) 个状态, 每次填充仅需 O(1) 时间, 时间复杂度为O(NW)。
 *  完全背包问题需要填充 ∑Ni=1⌊Wwi⌋∗(W\+1) 个状态, 每次填充仅需 O(1) 时间, 时间复杂度为 O(NW∑Ni=1⌊Wwi⌋)。
 *  还可以这样考虑：
    
    根据状态转移方程, 二维数组规模仍然为 N∗(W\+1), 每个状态需要计算 ⌊jwi⌋ 个结果的最大值, 即每次填充花费 O(⌊jwi⌋), 时间复杂度为 O(NW∑Ni=1⌊Wwi⌋)。

# 3. O(NW) 经典算法 #

以上解题策略在时间复杂度上并非最优, 每个状态的更新过程存在大量重复计算, 即 max(dp(i−1,j−kwi)\+kvi)。

* 假设, W=6, 第 i 种物品 wi=2, 状态更新计算量如下,
 
 <table> 
 <thead> 
 <tr> 
 <th align="center">k</th> 
 <th align="center">0</th> 
 <th align="center">1</th> 
 <th align="center">2</th> 
 <th align="center">3</th> 
 <th align="center">4</th> 
 <th align="center">5</th> 
 <th align="center">6</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center"> ⌊jwi⌋ </td> 
 <td align="center">0</td> 
 <td align="center">0</td> 
 <td align="center">1</td> 
 <td align="center">1</td> 
 <td align="center">2</td> 
 <td align="center">2</td> 
 <td align="center">3</td> 
 </tr> 
 <tr> 
 <td align="center">0</td> 
 <td align="center"> dp(i−1,j) </td> 
 <td align="center"> dp(i−1,j) </td> 
 <td align="center"> dp(i−1,j) </td> 
 <td align="center"> dp(i−1,j) </td> 
 <td align="center"> dp(i−1,j) </td> 
 <td align="center"> dp(i−1,j) </td> 
 <td align="center"> dp(i−1,j) </td> 
 </tr> 
 <tr> 
 <td align="center">1</td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"> dp(i−1,j−2)+vi </td> 
 <td align="center"> dp(i−1,j−2)+vi </td> 
 <td align="center"> dp(i−1,j−2)+vi </td> 
 <td align="center"> dp(i−1,j−2)+vi </td> 
 <td align="center"> dp(i−1,j−2)+vi </td> 
 </tr> 
 <tr> 
 <td align="center">2</td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"> dp(i−1,j−4)+2vi </td> 
 <td align="center"> dp(i−1,j−4)+2vi </td> 
 <td align="center"> dp(i−1,j−4)+2vi </td> 
 </tr> 
 <tr> 
 <td align="center">3</td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"></td> 
 <td align="center"> dp(i−1,j−6)+3vi </td> 
 </tr> 
 </tbody> 
 </table>
 * 若背包容量 j 从小到大增长, 对于同种物品数量增加的情况, 状态更新可借用同一行先前计算的结果, 从而降低时间复杂度。
 * 据此, 状态改变无非两种情况：
 
 (1) 增加同种物品数量, 即 dp(i,j−wi)\+vi
 
 (2) 准备开始添加下一种物品, 即 dp(i−1,j)
 * 状态转移方程为,
 
 dp(i,j)=max(dp(i−1,j),dp(i,j−wi)\+vi)
 * 对比0-1背包问题的状态转移方程,
 
 dp(i,j)=max(dp(i−1,j),dp(i−1,j−wi)\+vi)
 * 同样需要填充 N∗(W\+1) 个状态，每个状态计算的时间复杂度为 O(1), 故算法的时间复杂度为 O(NW)。

# 4. 算法优化 #

完全背包问题同样具有存储空间优化潜力, 即将存储空间由二维数组 \{ N∗(W\+1)\} 压缩为一维数组 \{ W\+1\}。

状态更新应采用顺序遍历, 即j从最小值开始, 从小到大更新dp数组。 原因有二：

(1) 0-1背包问题, 需要用到前行较小结果, 即 dp(i−1,j−wi);完全背包问题, 只需要用到前行同列结果, 不存在顺序覆盖问题。

(2) 完全背包问题, 需要用到同行较小结果, 顺序处理是必须的。

状态转移方程变为,

dp(j)=max(dp(j),dp(j−wi)\+vi)

# 5. 问题拓展 #

若将约束条件改为,总重量恰好等于背包容量, 拓展为**装满背包问题**。

处理思路与完全装满的0-1背包问题完全相同, 即修改数组初始化值为-INF, 且按照装满原则初始化首行。

# 6. 典型例题 #

Ver 2.0 2017-2-18