0-1背包问题的解法(动态规划、回溯算法)

0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi

问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

假设:

n = 5

w = [2,5,1,3,6]

v = [2,4,5,2,3]

c = 9

按照动态规划的五大步骤进行分析:

① 状态定义:要计算背包物品的总价值,我们可以设定一个空间来存储该总价值

② 状态转移方程:建模,创建一个二维数组dp[i][j],来表示第i个物品,背包容量为j的时候时候的最大价值。

③ 初始化值:默认我们将dp整个数组初始化为0,同时给w和v添加边界条件0,使得w = [0,2,5,1,3,6],
v = [0,2,4,5,2,3],那么为什么要这样做呢?

我们尝试分情况讨论一下:

(1)当 j<w[i],此时表示第i个物品的重量大于总背包容量,那么此时是无法装进该物品的。因此方程:dp[i][j]=dp[i-1][j]

(2)当j>=w[i],此时表示第i个物品的重量小于等于总背包量,这时候就需要根据最优性质原理,方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
因为当前物品的总价值,可能决定于前一个物品的总价值大,也可能决定于加上这个物品后得到的总价值。

(3)我们要从第i=1开始,所以需要添加一个边界0,防止越出异常。

④ 选取结果,选取dp[-1][-1]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# 回溯算法: 算法

# 使用备忘录来避免重复计算
import typing as t

item = [5, 6, 1, 2, 3]


def bag_0_1(something_i: int, total_in: int, total_bag: int, something_total: int):
"""
递归树模型,第i个物品不放入背包----左子树, 第i个物品放入背包----右子树
递归找到最后一个物品,从最后一个物品开始

:param total_in: 表示当前已经装进去物品的重量和
:param something_i: 表示装入到第几个物品
:param something_total: 表示总共有几个物品
:param total_bag: 表示背包总重量

剪枝
空间复杂度:O(n*m)
"""
max_num = 0
memorial: t.List = [[0 for _ in range(total_bag)] for _ in range(something_total)]

def dfs(i: int, total_inner: int):
nonlocal max_num
if total_inner == total_bag or i == something_total:
if total_inner > max_num:
max_num = total_inner
return
# 模拟右子树
if memorial[i][total_inner]:
return
memorial[i][total_inner] = 1
dfs(i + 1, total_inner)
if total_inner + item[i] <= total_bag:
# 模拟左子树
dfs(i + 1, total_inner + item[i])

dfs(something_i, total_in)

return max_num


res = bag_0_1(0, 0, 20, 5)
print(res)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

# 动态规划
import typing as t
def advance_bag_0_1_dp(items: t.List, items_value: t.List, number: int, total_bag: int) -> int:
"""
背包问题,求物品满足最大容量下时,物品价值也最大
动态规划求解
1.划分阶段:将问题划分为多个阶段
2.定义状态变量,起始值和返回值:在发展到每个阶段时的情况用状态变量表示出来
*3.状态转移方程:状态变化的参照,状态转移要根据前一阶段的状态推导出本阶段的状态。
4.寻找边界跳出条件:状态结束的条件
5.寻找是否能优化压缩空间
6.返回最终最优解
:param items: 物品重量
:param items_value: 物品价值集
:param number: 物品个数
:param total_bag: 背包总重量
:return: 可容纳最大容量

时间复杂度为0(m*n), 空间复杂度为O(m*n)

m为商品数量, n为包的大小
"""

if not items or number == 0:
return 0
if min(items) > total_bag:
return 0

# 定义状态变量
dp = [[0 for _ in range(total_bag)] for _ in range(number)]
dp[0][0], dp[0][items[0]] = 0, items_value[0]

for i in range(1, number):
for j in range(total_bag):
if j < items[i]:
# 如果位置小于物品重量,不将物品i加入背包,不计算其最大价值
dp[i][j] = dp[i - 1][j]
else:
# 取不加和加入背包后中的最大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i]] + items_value[i])
return max(dp[number - 1])


res = advance_bag_0_1_dp([2, 2, 4, 6, 3], [3, 5, 6, 1, 9], 5, 9)
print(res)

注:j从1开始,从0开始没有意义,因为初始化dp全为0,减小了m次循环的时间复杂度。