01 背包问题解析与代码
问题定义
给定一堆具有不同重量 { w 1 , w 2 , ⋯ , w n } \{ w_1,w_2, \cdots,w_n \} {w1,w2,⋯,wn}与价值 { v 1 , v 2 , ⋯ , v n } \{ v_1,v_2, \cdots,v_n \} {v1,v2,⋯,vn}的背包（knapsack），在总重量为 W 的情况下，如何选取背包才能获得最大价值？其中每种背包只能有被选取和不被选取两种选择。
思路解析
考虑解数组 d p [ i ] [ j ] dp[i][j] dp[i][j] ，其中的 i i i 表示尝试放入标号为 1 到 i 的背包， j j j 表示当前的限重为 j j j，数组中的值表示当前情况下可以取得的最大价值。
显然这个 dp 数组的第一行和第一列元素全为 0，逐个计算时我们使用从左到右，从上到下的原则进行计算，在计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 时，需要考虑两种情况:
第一种当前的总限重是不允许放入标号为 i 的背包的，也就是当前总限重小于标号为 i 的背包的重量，那么此时的最大价值应该等于总限重为 j，且尝试放入标号为 1-(i-1) 背包时的总价值，用公式表达：
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ( j < w [ i ] ) dp[i][j]=dp[i-1][j](j<w[i]) dp[i][j]=dp[i−1][j](j<w[i])
第二种则是当前的总限重是允许放入标号为 i 的背包的，也就是当前总限重大于标号为 i 的背包的重量，那么此时的最大价值又需要考虑两种情况，原因是放入标号为 i 的背包可能并不能取得最大价值。
放入标号为 i 的背包会产生多大的价值呢？这时我们就可以利用到先前已经计算好的解数组了，在放入标号为 i 的元素之后，背包限重变为 j - w[i]，那么放入 i-1（不包含第i个） 个背包，总限重为 j - w[i] 的情况下的最大价值就是 d p [ i − 1 ] [ j − w [ i ] ] dp[i-1][j-w[i]] dp[i−1][j−w[i]]，这时再加上标号 i 的背包总价值就是 d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i−1][j−w[i]]+v[i]
不放入标号为i的背包的价值则为 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]
所以，此时的最大价值应当比较上述两种情况，选取最大值
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) ( j ≥ w [ i ] ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(j \geq w[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])(j≥w[i])
这里提供一个在线练习 01背包数组填充的网站。
代码实现
def algo(weight, value, total):row = len(weight)col = total + 1res = [[0] * col for _ in range(row)]for i in range(1, row):for j in range(1, col):if weight[i] > j:res[i][j] = res[i-1][j]else:res[i][j] = max(res[i-1][j], res[i-1][j-weight[i]] + value[i])return resweight = [0, 4, 2, 3, 1]
value = [0, 9, 10, 4, 1]
total = 6print(algo(weight, value, total))
本文链接：https://my.lmcjl.com/post/2592.html
4 评论