第三天:《LeetCode一天一例》-----0-1背包问题(python实现)
0-1背包问题
题目: 给定物品的重量weights=[1, 2, 5, 6, 7] ,对应的价值values=[1, 6, 18, 22, 28] , 背包能装的最大重量为capicity=11。问:我们用这个背包装什么物品能获得最大价值? 注意:每件物品只有一件。并且最终重量不能超过背包所能承载的重量。
分析:
首先,说明一下,本题采用动态规划, 因为问题的本身含最优子结构。 我们先给出转态转移方程:
c(i, w) 表示包容量为w时,考虑前i个物品所能获得的最大价值。。 i表示第i个物品,w表示包容量
第一种情况: 当前物品的重量超过了包的承载量,显然装不上,那它当前的最大价值就是原有包中的价值(不装这个物品时的最大价值)。
第二种情况:当前物品的重量没有包承载量大。则说明当前这个物品可以装进去。 那我们就得考虑了: 装这个物品价值大还是不装这个物品价值大? 从两种情况中选最大的。
capicity | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
weight | value | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 6 | 0 | 1 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
5 | 18 | 0 | 1 | 6 | 7 | 7 | 18 | 19 | 24 | 25 | 25 | 25 | 25 |
6 | 22 | 0 | 1 | 6 | 7 | 7 | 18 | 22 | 24 | 28 | 29 | 29 | 40 |
7 | 28 | 0 | 1 | 6 | 7 | 7 | 18 | 22 | 28 | 29 | 34 | 35 | 40 |
上述就是本题手工计算得出的矩阵。 右下角的40, 就是我们所能获得的最大价值
接着,我们还需要输出获得最大价值的时候,我们拿了什么物品
从右下角的40开始, 背包容量为11,由于40 与上一行的40相等, 说明我们没有装第五个物品(因为当背包容量为11,装第四个物品的时候,价值已经到达了40)。 紧接着, 在背包容量为11时,对应第三个物品,最大价值是25, 所以,我们装了第四个物品。 此时,我们的背包容量变为W-w4 即:11-6=5。 所以,对于第三个物品,我们直接考虑在背包容量为5的时候, 可以看出价值是18,考虑有没有装第三个? 因为背包容量为5时,第二个物品所对应的最大价值为7. 所以我们装了第三个物品。 接在:W剩 - w3 = 5-5 = 0 。 我们就可以得出背包中装了第三个和第四个物品。
代码实现:
# 01 背包问题
def bag_01(weights, values, capicity):
# [*, *, *, *, *, *, *, *, *, *, *, *]
# [*, *, *, *, *, *, *, *, *, *, *, *]
# [*, *, *, *, *, *, *, *, *, *, *, *]
# [*, *, *, *, *, *, *, *, *, *, *, *]
# [*, *, *, *, *, *, *, *, *, *, *, *]
# [*, *, *, *, *, *, *, *, *, *, *, *]
n = len(values)
f = [[0 for j in range(capicity+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, capicity+1):
f[i][j] = f[i-1][j]
if j >= weights[i-1] and f[i][j] < f[i-1][j-weights[i-1]] + values[i-1]:
f[i][j] = f[i-1][j-weights[i-1]] + values[i-1]
return f
def show(capicity, weights, f):
n = len(weights)
print("最大价值:", f[n][capicity])
x = [False for i in range(n)]
j = capicity
for i in range(n, 0, -1):
if f[i][j] > f[i-1][j]:
x[i-1] = True
j -= weights[i-1]
print("背包中所装物品为:")
for i in range(n):
if x[i]:
print("第{}个".format(i+1))
if __name__ == '__main__':
# weights 指的是物品的重量
# values 指的是物品的价值
# capicity 指的是袋子能装的重量
n = 5
weights = [1, 2, 5, 6, 7]
values = [1, 6, 18, 22, 28]
capicity = 11
m = bag_01(weights, values, capicity)
# 打印矩阵
for i in range(len(m)):
print(m[i])
# 接下来输出要装的物品
show(capicity, weights, m)
输出结果: