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]:
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次循环的时间复杂度。