问题描述
有 N 件物品和一个容量是 V 的背包,假设每件物品只能使用一次。
且第 i 件物品的体积是 v[i] ,价值是 w[i] 。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数:$N$ ,$V$ ,用空格隔开,分别表示物品数量和背包容积。
接下来有 $N$ 行,每行两个整数 v[i] , w[i] ,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
解题思路
由于每个物品只能使用一次,因此对于每一个物品,都仅有放或者不放两种可能。
用子问题定义状态:即 f[i][j]
表示表示只看前 i 个物品,总体积是 j 的情况下,总价值最大是多少。
则对于第 i 个物品,由于有放或者不放两种可能:
不放:f[i][j] = f[i-1][j]
放:f[i][j] = f[i-1][j-v[i]] + w[i]
因此有状态转移方程为:f[i][j]=max{f[i-1][j], f[i-1][j-v[i]]+w[i]}
代码详解
def solution(N, V, v, w):
# 申请一个 res[N+1][V+1] 的数组
res = [[0]*(V+1) for j in range(N+1)]
for i in range(1, N+1):
for j in range(1, V+1):
if j >= v[i]:
res[i][j] = max((res[i-1][j], res[i-1][j-v[i]]+w[i]))
else:
res[i][j] = res[i-1][j]
return res
if __name__ == "__main__":
N, V = list(map(int, input().split()))
v = [0] * (N+1)
w = [0] * (N+1)
for i in range(1, N+1):
v[i], w[i] = list(map(int, input().split()))
res = solution(N, V, v, w)
print(res[N][V])
空间优化
以上方法的时间和空间复杂度都为 O(N*V)
,其中时间复杂度已经无法再进行优化,而空间复杂度可以优化到 O(V)
。
观察状态转移方程 f[i][j]=max{f[i-1][j], f[i-1][j-v[i]]+w[i]}
可以发现:
当前层的状态永远只依赖于上一层的状态,因此我们可以用户一维的状态 f[j]
来表示之前同样的状态。
在第 i 次循环之前,f[j]=f[i-1][j]
在第 i 次循环之后,f[j]=f[i][j]
因此我们的状态转移方程变为了 f[j]=max{f[j], f[j-v[i]]+w[i]}
注意:由于我们要保证 f[j-v[i]]
就相当于原来的 f[i-1][j-v[i]]
,所以我们的第二层循环需要改为逆序。
代码优化
def solution2(N, V, v, w):
# 申请一个 [V+1] 的数组
res = [0] * (V+1)
for i in range(1, N+1):
for j in range(V, 0, -1):
if j >= v[i]:
res[j] = max((res[j], res[j-v[i]]+w[i]))
return res[V]