一、为何可以用一维数组代替二维数组?
二维数组更新方式为
f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
可以看出f[i][:]只依赖于f[i-1][:],所以根本没必要保留之前的f[i-2][:]等状态值;
使得空间从o(n*m)缩小到o(m),n,m分别为物品个数和背包体积
其实每个物品的体积和价值在该层循环结束后也不会再用上,这里也可以压缩为两个o(1)的空间
二、为何要逆序更新?
一维数组更新方式为
while j >= v[i]:
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
我们只有上一层dp值的一维数组,更新dp值只能原地滚动更改;
注意到,当我们更新索引值较大的dp值时,需要用到索引值较小的上一层dp值dp[j - v[i]]
;
也就是说,在更新索引值较大的dp值之前,索引值较小的上一层dp值必须还在,还没被更新;
所以只能索引从大到小更新。
一维数组python代码
if __name__ == '__main__':
n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
v = [0 for i in range(n+1)]; w = [0 for i in range(m+1)]
for i in range(1, n + 1):
v[i], w[i] = list(map(int, input().split())) # 从索引1开始
# 一维数组
dp = [0 for i in range(m+1)]
for i in range(1, n + 1):# i 仍代表可以选择前i个物品
j = m
while j >= v[i]:
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
j -= 1
print(dp)
print('------------------')
print(dp[-1])
三、用样例解释,打印dp方便理解
将每一个i循环的dp打印出来就容易理解为何要逆序遍历j(限制物品总体积)
以更新第三层为例
更新索引5
i = 3, j = 5(m=5),v[3] = 3, w[3] = 4
当前更新第3层索引5 dp[5] = max(dp[5], dp[2] + 4)
注意,等号右边的dp[5],dp[2]都必须是上一层dp的对应索引值
此时第二层为[0, 2, 4, 6, 6, 6]
,第三层[0, 2(未改), 4(未改), 6(未改), 6(未改), 6(正在改)]
因为本层更新dp[5]时,只能使用未更新的dp值,这些才是上一层的dp值,即索引较小的最后更新
第三层索引5更新完后为[0, 2(未改), 4(未改), 6(未改), 6(未改), 8(已经改)]
更新索引4
i = 3, j = 4(m=5),v[3] = 3, w[3] = 4
此时进入j = 4
更新第三层索引4 dp[4] = max(dp[4], dp[1] + 4)
注意,等号右边的dp[4],dp[1]都必须是上一层dp的对应索引值
到这里就可以看出按索引从大到小求当前层dp值能保留上一层较小索引的dp值
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
n = 4, m = 5
第一层dp, i = 1, v[1] = 1 , w[1] = 2, dp[j] = max(dp[j], dp[j - v[1]] + w[1])
dp[j] = max(dp[j], dp[j - 1] + 2) j从5到1
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 2]
[0, 0, 0, 2, 2, 2]
[0, 0, 2, 2, 2, 2]
[0, 2, 2, 2, 2, 2]
------------------
第二层dp, i = 2, v[2] = 2 , w[2] = 4,
dp[j] = max(dp[j], dp[j - 2] + 4) j从5到2
[0, 2, 2, 2, 2, 6]
[0, 2, 2, 2, 6, 6]
[0, 2, 2, 6, 6, 6]
[0, 2, 4, 6, 6, 6]
------------------
第三层dp, i = 3, v[3] = 3 , w[3] = 4,
dp[j] = max(dp[j], dp[j - 3] + 4) j从5到3
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
------------------
第四层dp, i = 4, v[4] = 4 , w[4] = 5,
dp[j] = max(dp[j], dp[j - 4] + 5) j从5到4
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
------------------
8
二维数组朴素方法(简单易懂也能AC)
if __name__ == '__main__':
N = 1010
n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
v = [0 for i in range(N)]; w = [0 for i in range(N)]
for i in range(1, n + 1):
v[i], w[i] = list(map(int, input().split())) # 从索引1开始
f = [[0 for i in range(N)] for j in range(N)] # 二维数组存储当前状态可达到的最大价值
# 朴素方法
i = 1
while i <= n:
j = 0
while j <= m:
f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
j += 1
i += 1
for i in range(len(f)):
print(f[i])
print(f[n][m])
%%%
真的牛
很赞
tql,最牛逼的讲解也最通俗易懂!
newbee
老公newbee
我终于看到有人写执行过程中的数组了,看懂了,感谢楼主
看了那么多题解,你是讲到点子上了,赞!!!
看懂了!感谢!楼主其他题解也很nice~大赞!!!
tql,每次看01背包都不懂,这次终于懂了,谢谢楼主
感谢
终于懂了一维数组逆序的原因,非常感谢。
楼主真的很用心,赞一个