前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >动态规划（二）：0-1背包

动态规划（二）：0-1背包

作者头像
zhipingChen
发布于 2018-09-13 15:45:39
9180
发布于 2018-09-13 15:45:39
举报
文章被收录于专栏：编程理解编程理解

题目

有

N
N

件物品，每件占据的空间大小为

w_i
w_i

、价值为

v_i(1\le i\le N)
v_i(1\le i\le N)

，对于容量空间为

V
V

的背包，问能够承载的最大价值是多少

分析

对于第

i
i

件物品

(1\le i\le N)
(1\le i\le N)

，只有两种状态，放入背包，或不放入背包。所以在空间大小为

j
j

时

(0\le j\le V)
(0\le j\le V)

，能够承载的最大价值根据第

i
i

件物品放入或不放入而定，且只有这两种情况。

解答

以

F(i,j)
F(i,j)

表示物品数量为

i
i

，空间大小为

j
j

时的最大价值。则有：

  1. 当
i==1,j\lt w_i
i==1,j\lt w_i

时有：

F(i,j)=0
F(i,j)=0

，表示当前空间大小

j
j

无法容纳第一件物品，所以价值为

0
0

；

  1. 当
i ==1,j\ge w_i
i ==1,j\ge w_i

时有：

F(i,j)=v_i
F(i,j)=v_i

，表示当前空间大小

j
j

可以容纳第一件物品，所以价值为

v_i
v_i

；

  1. 当
2\le i\le N,j\lt w_i
2\le i\le N,j\lt w_i

时有：

F(i,j)=F(i-1,j)
F(i,j)=F(i-1,j)

，表示当前空间大小

j
j

无法容纳第

i
i

件物品，所以价值为

i-1
i-1

件物品时的价值

F(i-1,j)
F(i-1,j)

；

  1. 当
2\le i\le N,j\ge w_i
2\le i\le N,j\ge w_i

时有：

F(i,j)=max[F(i-1,j),F(i-1,j-w_i)+v_i]
F(i,j)=max[F(i-1,j),F(i-1,j-w_i)+v_i]

，表示当前空间大小

j
j

可以容纳第

i
i

件物品，所以价值取决于第

i
i

件物品放入或不放入哪一种情况价值更大；

对于

i
i

件物品，空间大小为

j
j

时：

  • 不放入第
i
i

件物品时价值为

F(i-1,j)
F(i-1,j)

，即将所有空间

j
j

施加于前

i-1
i-1

件物品上；

  • 放入第
i
i

件物品时，价值为

F(i-1,j-w_i)+v_i
F(i-1,j-w_i)+v_i

，即第

i
i

件物品的价值与

j-w_i
j-w_i

空间下前

i-1
i-1

件物品的价值之和。

对于 01 背包问题，有两种描述，背包能够承载的最大价值、背包刚好装满时承载的最大价值。第二种描述增加了“装满”的条件约束，两种情况很类似，下面分别对无约束和有约束的情况进行讨论。

无装满约束

二维数组形式
代码语言：javascript
复制
def backpack(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [[] for i in range(N)]  # Two-dimensional array
    for i in range(N):
        for j in range(V + 1): 
            if j < weightArr[i]:  # the space can not afford the element's weight
                arr[i].append(0 if i == 0 else arr[i - 1][j])
            else:  # the space can afford the element's weight
                if i == 0:  
                    arr[0].append(valueArr[0])
                else:
                    arr[i].append(max(arr[i - 1][j], arr[i - 1][j - weightArr[i]] + valueArr[i]))
        arr[i] = arr[i]
    return arr[-1][-1]

代码中存在两层循环，以二维数组的形式记录中间数据，分别记录不同物品个数在各个空间大小下的最大价值。循环内部存在两种判断，分别用于判断空间大小

j
j

是否能够容纳第

i
i

件物品，和判断当前是否是第一件物品。

  • 若
j \lt weightArr[i]
j \lt weightArr[i]

，即当前空间无法容纳第

i
i

件物品，则继续判断是否是第一件物品，若

i == 0
i == 0

，即当前是第一件物品，则

F(i,j)=0
F(i,j)=0

，表示当前空间大小无法容纳第一件物品，最大价值为

0
0

；若

i \gt 0
i \gt 0

，即当前不是第一件物品，则

F(i,j)=F(i-1,j)
F(i,j)=F(i-1,j)

，表示当前空间大小无法容纳第

i
i

件物品，最大价值等同于没有第

i
i

件物品时候的最大价值；

  • 若
j \ge weightArr[i]
j \ge weightArr[i]

，即当前空间可以容纳第

i
i

件物品，则继续判断是否是第一件物品，若

i == 0
i == 0

，即当前是第一件物品，则

F(i,j)=valueArr[0]
F(i,j)=valueArr[0]

，表示当前空间可以容纳第一件物品，因为只有第一件物品，所以最大价值为

valueArr[0]
valueArr[0]

；若

i \gt 0
i \gt 0

，即当前不是第一件物品，则

F(i,j)=max[F(i-1,j),F(i-1,j-w_i)+v_i]
F(i,j)=max[F(i-1,j),F(i-1,j-w_i)+v_i]

，比较第

i
i

件物品放入或不放入的价值，选择出最大价值。

代码中存在两层循环，时间复杂度为

O(NV)
O(NV)

，使用了二维数组作为存储空间，空间复杂度为

O(NV)
O(NV)

。

观察推导公式：

F(i,j)=max[F(i-1,j),F(i-1,j-w_i)+v_i]
F(i,j)=max[F(i-1,j),F(i-1,j-w_i)+v_i]

，可以发现

F(i,j)
F(i,j)

的值只与

F(i-1,j)
F(i-1,j)

和

F(i-1,j-w_i)
F(i-1,j-w_i)

有关，对应到二维数组中即为，

arr[i][j]
arr[i][j]

的值只与

arr[i-1][j]
arr[i-1][j]

和

arr[i-1][j-weightArr[i]]
arr[i-1][j-weightArr[i]]

有关。所以若已知二维数组第

i-1
i-1

行的数组

arr[i-1]
arr[i-1]

，则推导第

i
i

行数组数据时，若从右向左推导，或者称为

j
j

值下标由大到小推导，则第

i
i

行数据可以覆盖在第

i-1
i-1

行数组。所以可以将二维数组空间优化为一维数组空间。

一维数组形式
代码语言：javascript
复制
def backpack2(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [0] * (V + 1)  # One-dimensional array
    for i in range(N):
        for j in range(V, -1, -1):
            if j >= weightArr[i]:
                arr[j] = max(arr[j], arr[j - weightArr[i]] + valueArr[i])
    return arr[-1]

代码中仍存在两层循环，第二层循环中变量值

j
j

由大到小变化，循环体中仍存在判断，不过因为只存在一维数组，且数组元素初始化值为

0
0

，所以不需要再判断是否是第一件物品。

代码中存在两层循环，时间复杂度为

O(NV)
O(NV)

，使用了一维数组作为存储空间，空间复杂度为

O(V)
O(V)

。

其实无论一维数组或者二维数组形式，第二层循环范围不一定非要是 0 ~

V
V

，因为此处只讨论 01 背包，所以若题目中给出的

V
V

值很大，大到即便将

N
N

件物品全部放入背包中，仍存在较大容量空闲的话，这种情况可以修改第二层循环范围为 0 ~

\sum_{i=1}^{N}w_i
\sum_{i=1}^{N}w_i

。

有装满约束

二维数组形式
代码语言：javascript
复制
def backpackComplete(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [[] for i in range(N)]  # Two-dimensional array
    for i in range(N):  
        for j in range(V + 1): 
            if j < weightArr[i]:  # the space can not afford the element's weight
                arr[i].append(arr[i - 1][j] if i > 0 else None)
            else:  # the space can afford the element's weight
                if i == 0:  
                    arr[0].append(valueArr[0] if j == weightArr[i] else None)
                else:
                    if arr[i - 1][j] and arr[i - 1][j - weightArr[i]]:  # the two values both exist
                        arr[i].append(max(arr[i - 1][j], arr[i - 1][j - weightArr[i]] + valueArr[i]))
                    elif not arr[i - 1][j] and not arr[i - 1][j - weightArr[i]]:  # the two values both not exist
                        arr[i].append(valueArr[i] if j == weightArr[i] else None)
                    else:  # only one value exist
                        arr[i].append(arr[i - 1][j] if arr[i - 1][j] else arr[i - 1][j - weightArr[i]] + valueArr[i])
        arr[i] = arr[i]
    return arr[-1][-1]

有装满约束与无装满约束较为类似，同样的两层循环，同样的两种判断。不同之处在于，当空间大小

j
j

不能刚好等于物品占据空间之和时，此时的价值为

None
None

。所以此处的代码相对于无装满约束的代码，最直观的差异就是，当空间大小

j \ge weightArr[i]
j \ge weightArr[i]

且

i\gt 0
i\gt 0

，通过推导公式求最大价值时，对

arr[i-1][j]
arr[i-1][j]

和

arr[i-1][j-weightArr[i]]
arr[i-1][j-weightArr[i]]

是否为

None
None

进行了判断。

一维数组形式
代码语言：javascript
复制
def backpackComplete2(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [None] * (V + 1)  # One-dimensional array
    for i in range(N):
        for j in range(V, -1, -1):
            if j >= weightArr[i]:
                if arr[j] and arr[j - weightArr[i]]:  # the two values both exist
                    arr[j] = max(arr[j], arr[j - weightArr[i]] + valueArr[i])
                elif not arr[j] and not arr[j - weightArr[i]]:  # the two values both not exist
                    arr[j] = valueArr[i] if j == weightArr[i] else None
                else:  # only one value exist
                    arr[j] = arr[j] if arr[j] else arr[j - weightArr[i]] + valueArr[i]
    return arr[-1]

比较有、无装满约束的一维数组形式，可以发现与二维数组同样的差异，即空间大小不刚好满足物品占据空间之和时，价值为

None
None

，且对推导公式中的元素值进行了是否为

None
None

判断。

有、无装满约束，算法的时间复杂度和空间复杂度不变。不过可以发现一个很明显的地方：有装满约束时，数组的最后一项元素值

arr[-1][-1]
arr[-1][-1]

或

arr[-1]
arr[-1]

不一定是数组中的最大元素，而数组中的最大元素值一定等于无装满约束时数组的最后一项元素值。

本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.09.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
其他

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ，欢迎热爱写作的你一起参与！

其他
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 题目
  • 分析
  • 解答
  • 无装满约束
    • 二维数组形式
      • 一维数组形式
      • 有装满约束
        • 二维数组形式
          • 一维数组形式
          领券

          腾讯云开发者

          扫码关注腾讯云开发者

          扫码关注腾讯云开发者

          领取腾讯云代金券

          热门产品

          热门推荐

          更多推荐

          Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

          深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

          腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

          Copyright © 2013 - 2024 Tencent Cloud.

          All Rights Reserved. 腾讯云 版权所有

          登录 后参与评论