背包问题
0-1 背包 不可分割
有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
1. 用v[i]表示物品价值，w[i]表示物品重量。定义状态dp[i][j]以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值。
2. 初始化边界条件，V(0,j)=V(i,0)=0；
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)；
因此：
第一，包的容量比该商品体积小，装不下，此时的价值与前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) ｝
number, capacity = 4, 8 w = [0, 2, 3, 4, 5] v = [0, 3, 4, 5, 6] dp = [[0] * (capacity + 1) for _ in range(number + 1)] for i in range(number + 1): for j in range(capacity + 1): if i == 0: dp[i][j] = 0 elif j == 0: dp[i][j] = 0 else: if j < w[i]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i]) print(dp) print(dp[number][capacity])
完全背包问题
有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。 每个物品有无限个
number, capacity = 3, 5 w = [0, 3, 2, 2] v = [0, 5, 10, 20] dp = [[0] * (capacity + 1) for _ in range(number + 1)] for i in range(number + 1): for j in range(capacity + 1): if i == 0: dp[i][j] = 0 elif j == 0: dp[i][j] = 0 else: nCount = j // w[i] for k in range(nCount + 1): dp[i][j] = max(dp[i][j], dp[i-1][j - k*w[i]] + k * v[i]) print(dp) print(dp[number][capacity])
背包问题可分割
m = eval(input('可承载的最大重量：'))
h = eval(input('宝物重量：'))
v = eval(input('宝物价值：'))
# 计算权重, 整合得到一个数组
arr = [(i,v[i]/h[i], h[i], v[i]) for i in range(len(h))]
# 按照list中的权重，从大到小排序
arr.sort(key=lambda x:x[1], reverse=True) # list.sort() list排序函数
bagVal = 0
bagList = []
for i,w,h,v in arr:
# 1 如果能放的下宝物，那就把宝物全放进去
if w <= m:
m -= h
bagVal += v
bagList.append(i)
# 2 如果宝物不能完全放下，考虑放入部分宝物
else:
bagVal += m * w
bagList.append(i)
break
print('\n排序后：',arr)
print('能运走的最大价值：%.2f'%bagVal,'此时承载的宝物有：',bagList) 
查看12道真题和解析