0 1 背包问题描述
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8
i（物品编号） 1 2 3 4
w（体积） 2 3 4 5
v（价值） 3 4 5 6
解题思路
为描述方便，首先定义一些变量：Vi表示第i个物品的价值，Wi表示第i个物品的体积，定义V（i，j）为当前背包容量j,前i个物品的最佳组合对应的价值，同时将背包问题抽象化（X1,X2,...,Xn, 其中Xi取0或1，表示第i个物品选或不选）。
1、建立模型，即求max(V1X1+V2X2+....+VnXn)
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；
由此可以得出递推关系式：
j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝
解题代码
python 解法：
#!/bin/bash python
#coding:utf-8
def calMaxValue(w, v, c):
"""
计算0,1背包最佳组合方案
w: 物品的重量list
v: 物品的价值list
c: 背包重量
"""
w_len = len(w)
w.insert(0, 0)
v.insert(0, 0)
dp = [[0 for _ in range(c + 1)] for _ in range(w_len + 1)]
for i in range(1, w_len + 1):
for j in range(1, c + 1):
if w[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
return dp[w_len][c]
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
c = 8
num = calMaxValue(w, v, c)
print(num)
带经过节点的写法：
#!/bin/bash python
#coding:utf-8
def calMaxValue(w, v, c):
"""
计算0,1背包最佳组合方案
w: 物品的重量list
v: 物品的价值list
c: 背包重量
"""
w_len = len(w)
w.insert(0, 0)
v.insert(0, 0)
dp = [[0 for _ in range(c + 1)] for _ in range(w_len + 1)]
for i in range(1, w_len + 1):
for j in range(1, c + 1):
if w[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
i = w_len
j = c
l = []
while i > 0:
if dp[i][j] == dp[i - 1][j]:
i = i - 1
elif w[i] <= j and dp[i][j] == dp[i - 1][j - w[i]] + v[i]:
l.insert(0, i)
j = j - w[i]
i = i - 1
print(l)
return dp[w_len][c]
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
c = 8
num = calMaxValue(w, v, c)
print(num)
参考文章：https://blog.csdn.net/qq_38410730/article/details/81667885
完全背包
完全背包，和0，1背包的区别在于，每件物品的数量无限，解法与0，1背包相似，推导公式要有一点变化，
V[i][j] = max(V[i -1][j], V[i][j - w[i]] + v[i]),因为放入一个i之后，还可以再放入i。
#!/bin/bash python
#coding:utf-8
def calMaxValue(w, v, c):
"""
计算完全背包最佳组合方案
w: 物品的重量list
v: 物品的价值list
c: 背包重量
"""
w_len = len(w)
w.insert(0, 0)
v.insert(0, 0)
dp = [[0 for _ in range(c + 1)] for _ in range(w_len + 1)]
for i in range(1, w_len + 1):
for j in range(1, c + 1):
if w[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])
i = w_len
j = c
res = {}
while i > 0:
# 循环取i，直到取不到为止
while w[i] <= j and dp[i][j] == dp[i][j - w[i]] + v[i]:
res[i] = res.get(i, 0) + 1
j = j - w[i]
i -= 1
print(res)
return dp[w_len][c]
w = [1, 3, 4, 7]
v = [2, 3, 5, 9]
c = 10
num = calMaxValue(w, v, c)
print(num)
多重背包
多重背包和完全背包，以及0，1背包的区别在于，多重背包中每个物品的个数都是给定的。
新的推导公式为V[i][j] = max(V[i-1][j], V[i - 1][j - k * w[i]] + k *v[i])，其中k为放了几次编号为i的物品。
多重背包还有种解法，是讲多重背包按数目展开，变成0，1背包问题。
#!/bin/bash python
#coding:utf-8
def calMaxValue(w, v, n, c):
"""
计算多重背包最佳组合方案
w: 物品的重量list
v: 物品的价值list
n: 物品的数量
c: 背包重量
"""
w_len = len(w)
w.insert(0, 0)
v.insert(0, 0)
n.insert(0, 0)
dp = [[0 for _ in range(c + 1)] for _ in range(w_len + 1)]
for i in range(1, w_len + 1):
for j in range(1, c + 1):
if w[i] > j:
dp[i][j] = dp[i - 1][j]
else:
count = min(n[i], j/w[i])
dp[i][j] = dp[i - 1][j]
for k in range(1, count + 1):
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i])
print[dp]
i = w_len
j = c
res = {}
while i > 0:
count = min(n[i], j / w[i])
for k in range(count, 0, -1):
# 去满足的最大k值
if dp[i][j] == dp[i - 1][j - k * w[i]] + k * v[i]:
res[i] = k
j = j - k * w[i]
break;
i -= 1
print(res)
return dp[w_len][c]
w = [1, 2, 2]
v = [6, 10, 20]
n = [10, 5, 2]
c = 8
num = calMaxValue(w, v, n, c)
print(num)
网友评论