一、二维dp
dp[i][j]表示在背包容量为j且考虑物品i时的最大价值,那么dp[i][j]可由dp[i - 1]推出,即对第i个物品是取还是不取,取第i个物品即为dp[i - 1][j - v[i]] + w[i],因为取第i个物品时的最大价值实际上还是从第i - 1个物品处推得的,而且取第i个物品还需要在第i - 1个物品时的背包容量减去物品i的体积才能表示取到了物品i。
不取物品i则表示为dp[i - 1][j],即体积不变。
因此,就确定了递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
剩下的遍历顺序怎么考虑呢?因为dp[i][j]可由dp[i - 1][j]与dp[i - 1][j - v[i]]推出,所以可以从i, j 的左上方推得。因此就是从大到小遍历。
N, V = map(int, input().split())
v, w = [0] * (N + 1), [0] * (N + 1)
dp = [[0 for _ in range(V + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
v[i], w[i] = map(int, input().split())
for i in range(1, N + 1):
for j in range(V + 1):
dp[i][j] = dp[i - 1][j]
if j >= v[i]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i])
print(dp[N][V])
二、空间优化,一维dp
从上面的代码中我们能发现,其实有用的信息都在最后一层,之前层的都在循环中使用一次之后就不再使用了,因此我们可以只需要一维的数组就能解决这个问题了~
具体如何解决呢?如果直接将dp[i - 1][j - v[i]]中的第一维去掉的话,那么从小到大遍历的时候就会用到第i层中的dp[j - v[i]],而不是第i - 1层,因为在遍历过程中dp[j - v[i]]已经先于dp[j]被遍历了。
因此,我们可以从大到小遍历,这样始终保证的是取的上一层的值。如下:
N, V = map(int, input().split())
v, w = [0] * N, [0] * N
for i in range(N):
v[i], w[i] = map(int, input().split())
dp = [0] * (V + 1)
for i in range(N):
for j in range(V, v[i] - 1, -1):
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
print(dp[V])