0-1 背包问题——动态规划（一）

心已赠人 2022-07-12 05:25 149阅读 0赞

### 文章目录 ###

*  1. 问题描述
 *  2. 数学描述
 *  3. 解题思路
 *  4. 算法优化
 *  5. 问题拓展
 *  6. 典型例题

# 1. 问题描述 #

有  N N N 种物品，物品  i i i 的重量为  w i w\_i wi，价格为  v i v\_i vi，背包所能容纳的最大重量为  W W W，求背包内装入物品总价值的最大值。其中， N , W , w i , v i ≥ 0 N, W, w\_i, v\_i \\geq 0 N,W,wi,vi≥0。

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

# 2. 数学描述 #

约束条件：  
 (1) \{ ∑ i = 1 N w i x i ≤ W x i ∈ \{ 0 , 1 \}      ( 1 ≤ i ≤ N ) \\left\\\{\\begin\{aligned\} & \\sum\_\{i=1\}^N w\_ix\_i \\leq W \\tag\{1\} \\\\ & x\_i \\in \\\{0,1\\\} \\ \\ \\ \\ (1 \\leq i \\leq N) \\end\{aligned\} \\right. ⎩⎪⎪⎨⎪⎪⎧i=1∑Nwixi≤Wxi∈\{ 0,1\}    (1≤i≤N)(1)

目标函数：  
 (2) ∑ i = 1 N v i x i \\begin\{aligned\} & \\sum\_\{i=1\}^N v\_ix\_i \\tag\{2\} \\end\{aligned\} i=1∑Nvixi(2)

该问题可以描述为：求满足约束条件 (1)，同时使目标函数 (2) 最大的解向量  X = ( x 1 , x 2 , ⋯ &ThinSpace; , x N ) X = (x\_1, x\_2, \\cdots ,x\_N) X=(x1,x2,⋯,xN)。

# 3. 解题思路 #

**0-1 背包**是一类经典的动态规划问题，求解关键在于推倒递推公式。

*  设  N N N 为物品总数， W W W 为背包最大容纳重量，定义一个规模为  N ∗ ( W + 1 ) N \* (W+1) N∗(W\+1) 的二维数组。这里以  N = 5 N = 5 N=5， W = 10 W =10 W=10 为例说明。
 *   d p ( i , j ) dp(i,j) dp(i,j) 表示可选前  i i i 件物品，在背包容量为  j j j 时，背包内装入物品的最大值 。
 *  自上向下，自左向右，填充该二维数组。

1.  第一行，可选物品仅为 ①。

d p ( 1 , j ) = \{ 0      j ∈ \[ 0 , 2 ) 6      j ∈ \[ 2 , 10 \] dp(1,j)= \\left\\\{\\begin\{aligned\} & 0 \\ \\ \\ \\ j \\in \[0,2) \\\\ & 6 \\ \\ \\ \\ j \\in \[2,10\] \\end\{aligned\} \\right. dp(1,j)=\{ 0    j∈\[0,2)6    j∈\[2,10\]

1.  第二行，可选物品为 ①②，可借助第一行结果进行计算。这两行的区别仅在于物品 ② 是否应该放入，有两种情况：  
    （1） 不放入物品 ②，背包总价值不变，即  d p ( 2 , j ) = d p ( 1 , j ) dp(2,j) = dp(1,j) dp(2,j)=dp(1,j)  
    （2） 放入物品 ②，背包应保证足够剩余容量，也就是在  d p ( 1 , j − w 2 ) dp(1,j-w\_2) dp(1,j−w2) 的基础上放入，即  d p ( 2 , j ) = d p ( 1 , j − w 2 ) + v 2 dp(2,j) = dp(1,j-w\_2) + v\_2 dp(2,j)=dp(1,j−w2)\+v2

二者取最大值，即  d p ( 2 , j ) = m a x ( d p ( 1 , j ) , d p ( 1 , j − w 2 ) + v 2 ) dp(2,j) = max(dp(1,j),dp(1,j-w\_2) + v\_2) dp(2,j)=max(dp(1,j),dp(1,j−w2)\+v2)

1.  第  i i i 行，可选物品为  \{ 1 , ⋯ &ThinSpace; , i \} \\\{1, \\cdots ,i\\\} \{ 1,⋯,i\}，借助第  i − 1 i-1 i−1 行结果进行计算。这两行的区别仅在于物品  i i i 是否应该放入，有两种情况：  
    （1） 不放入物品  i i i，背包总价值不变，即  d p ( i , j ) = d p ( i − 1 , j ) dp(i,j) = dp(i-1,j) dp(i,j)=dp(i−1,j)  
    （2） 放入物品  i i i，背包应保证足够剩余容量，也就是在  d p ( i − 1 , j − w i ) dp(i-1,j-w\_i) dp(i−1,j−wi) 的基础上放入，即  d p ( i , j ) = d p ( i − 1 , j − w i ) + v i dp(i,j) = dp(i-1,j-w\_i) + v\_i dp(i,j)=dp(i−1,j−wi)\+vi

二者取最大值，即  d p ( i , j ) = m a x ( d p ( i − 1 , j ) , d p ( i − 1 , j − w i ) + v i ) dp(i,j) = max(dp(i-1,j),dp(i-1,j-w\_i) + v\_i) dp(i,j)=max(dp(i−1,j),dp(i−1,j−wi)\+vi)

综上，状态转移方程为：

(1) d p ( 1 , j ) = \{ 0      0 ≤ j < w 1 v 1      j ≥ w 1 dp(1,j)= \\left\\\{\\begin\{aligned\} & 0 \\ \\ \\ \\ 0 \\leq j < w\_1 \\tag\{1\} \\\\ & v\_1 \\ \\ \\ \\ j \\geq w\_1 \\end\{aligned\} \\right. dp(1,j)=\{ 0    0≤j<w1v1    j≥w1(1)

(2) d p ( i , j ) = \{ d p ( i − 1 , j )      0 ≤ j < w i m a x ( d p ( i − 1 , j ) , d p ( i − 1 , j − w i ) + v i )      j ≥ w i dp(i,j)= \\left\\\{\\begin\{aligned\} & dp(i-1,j) \\ \\ \\ \\ 0 \\leq j < w\_i \\tag\{2\} \\\\ & max(dp(i-1,j),dp(i-1,j-w\_i) + v\_i) \\ \\ \\ \\ j \\geq w\_i \\end\{aligned\} \\right. dp(i,j)=\{ dp(i−1,j)    0≤j<wimax(dp(i−1,j),dp(i−1,j−wi)\+vi)    j≥wi(2)

求解过程就是填充规模为  \{ N ∗ ( W + 1 ) \} \\\{N \* (W+1)\\\} \{ N∗(W\+1)\} 的二维数组，每次填充仅需  O ( 1 ) \\mathcal\{O\}(1) O(1) 时间，故算法的时间复杂度为  O ( N W ) \\mathcal\{O\}(NW) O(NW)。

**动态规划特点总结**：

1.  问题分解。将大问题转化为子问题，借助子问题的结果求解大问题。
2.  状态转移。每个子问题或者子子问题的求解结果都视为一个状态，状态转移过程即问题的转化、复合过程。
3.  记忆化搜索。用空间换时间，存储子问题的结果作为后续大问题求解的已知条件。

# 4. 算法优化 #

以上过程存在空间优化潜力，计算第  i i i 行时，仅用到了第  i + 1 i+1 i\+1 行结果。存储空间可以由二维数组  N ∗ ( W + 1 ) N\*(W+1) N∗(W\+1) 压缩为一维数组  W + 1 W+1 W\+1。

状态更新过程应采用逆序遍历，即  j j j 从最大值开始，从大到小更新数组。若采用顺序更新,  d p ( j − w i ) dp(j-w\_i) dp(j−wi) 更新在前、使用在后，导致  i − 1 i-1 i−1 行结果在未被使用之前就被覆盖了。

状态转移方程为,

d p ( j ) = \{ m a x ( d p ( j ) , d p ( j − w i ) + v i )      j ≥ w i d p ( j )      0 ≤ j < w i dp(j)= \\left\\\{\\begin\{aligned\} & max(dp(j),dp(j-w\_i) + v\_i) \\ \\ \\ \\ j \\geq w\_i \\\\ & dp(j) \\ \\ \\ \\ 0 \\leq j < w\_i \\end\{aligned\} \\right. dp(j)=\{ max(dp(j),dp(j−wi)\+vi)    j≥widp(j)    0≤j<wi

# 5. 问题拓展 #

以上问题的约束条件为,

(1) ∑ i = 1 N w i x i ≤ W \\begin\{aligned\} \\sum\_\{i=1\}^N w\_ix\_i \\leq W \\tag\{1\} \\end\{aligned\} i=1∑Nwixi≤W(1)

(2) x i ∈ \{ 0 , 1 \}      ( 1 ≤ i ≤ N ) \\begin\{aligned\} x\_i \\in \\\{0,1\\\} \\ \\ \\ \\ (1 \\leq i \\leq N) \\tag\{2\} \\end\{aligned\} xi∈\{ 0,1\}    (1≤i≤N)(2)

*  约束条件（1），要求物品总重量不得超过背包容量，允许未装满。约束条件变为要求总重量恰好等于背包容量，拓展为**背包装满问题**。
 *  约束条件（2），要求每种物品仅有一件。约束条件变为物品件数不限，拓展为第二类问题**完全背包问题**。

# 6. 典型例题 #

*  [hdu 2602 - Bone Collector][]

[hdu 2602 - Bone Collector]: http://blog.csdn.net/moonspiritacm/article/details/55051635