0 1背包问题
0 1背包问题
""" 0 1 背包问题 """
def bag(wgt, val, cap):
n = len(wgt)
dp = [[0]*(cap+1) for _ in range(n+1)]
for i in range(1, n+1):
for c in range(1, cap + 1):
if wgt[i - 1] > c:
dp[i][c] = dp[i-1][c]
else:
dp[i][c] = max(dp[i-1][c], dp[i-1][c-wgt[i-1]] + val[i - 1])
return dp[n][cap]
if __name__ == "__main__":
wgt = [3, 2, 1]
val = [15, 11, 5]
cap = 4
# 动态规划
res = bag(wgt, val, cap)
print(f"不超过背包容量的最大物品价值为 {res}")介绍
用一个矩阵记录 01 背包问题的最优解， dp[i][c] 表示背包容量为c，在前i 个物品中进行选择的最优解的价值。 dp[i][c] 这个状态 是从 dp[i-1]c 或 dp[i-1][c- wgt[i-1]] + val(i - 1) (前 i-1 个 物品 ， 容量减去现在要添加的物品的重量 的 最优解 再 加上现在要添加的物品的价值)。 即两种情况，当面临是否挑选第i个物品的选择时， 添加还是不添加， 添加的话，要放弃已经装好的等于当前物品的重量， 再去添加当前物品;不添加的话， 当前状态的最优解也就是i-1 c 状态时的最优解了。所以是 dp[i][c] = max(dp[i-1][c], dp[i-1][c-wgt[i-1]] + val[i - 1])。
空间优化
上述代码所使用的矩阵dp其时在每个循环中所需要的只有一行， 完全可以用一个数组来表示，以节省空间。 可以观察到， 最优解的计算与上一层的dp[i-1][c] 以及dp[i-1][c- wgt[i-1]] 有关， 采用数组保存状态，如果继续从左往右遍历， 会在还没有计算到i层相应c容量时就覆盖掉[i-1]层计算得到的最优解， 因此从右往左遍历，这样可以保证再计算完i层相应容量最优解时 再覆盖掉i-1层记录的最优解。
""" 0 1 背包问题 """
def bag(wgt, val, cap):
n = len(wgt)
dp = [0 for _ in range(cap+1)]
for i in range(1, n+1):
for c in range(cap, 0, -1):
if wgt[i - 1] > c:
dp[c] = dp[c]
else:
dp[c] = max(dp[c], dp[c-wgt[i-1]] + val[i - 1])
return dp[cap]
if __name__ == "__main__":
wgt = [3, 2, 1]
val = [15, 11, 5]
cap = 4
# 动态规划
res = bag(wgt, val, cap)
print(f"不超过背包容量的最大物品价值为 {res}")完全背包问题
""" 完全背包问题 """
def bag(wgt, val, cap):
dp = [[0]*(cap + 1) for _ in range(len(wgt) + 1)]
for i in range(len(wgt)+1):
for c in range(cap + 1):
if wgt[i-1] > c:
dp[i][c] = dp[i-1][c]
else:
dp[i][c] = max(dp[i-1][c], dp[i][c-wgt[i-1]]+ val[i-1])
return dp[len(wgt)][cap]
if __name__ == "__main__":
wgt = [3, 2, 1]
val = [15, 11, 5]
cap = 4
# 动态规划
res = bag(wgt, val, cap)
print(f"不超过背包容量的最大物品价值为 {res}")介绍
完全背包问题的代码和0 1背包问题的区别就就只有一行 dp[i][c] = max(dp[i-1][c], dp[i][c-wgt[i-1]]+ val[i-1]) 0 1 背包问题 当前状态只能由没有挑选过当前物品 的 前 i-1 层状态变化而来 而 完全背包问题， 可以从已经添加过 当前物品的 同层， 即前 i 层的状态变化而来。
空间优化
每一层的元素，由同层的d[i][c-wgt[i]]以及正上方元素确定， 当从左往右遍历时， 正上方元素恰好不会被修改， 以及d[i][c-wgt[i]]会生成， 所以从左往右遍历， 只用一个 数组，达到优化空间的目的。
""" 完全背包问题 """
def bag(wgt, val, cap):
dp = [0 for _ in range(cap + 1)]
for i in range(len(wgt)+1):
for c in range(cap + 1):
if wgt[i-1] > c:
dp[c] = dp[c]
else:
dp[c] = max(dp[c], dp[c-wgt[i-1]]+ val[i-1])
return dp[cap]
if __name__ == "__main__":
wgt = [3, 2, 1]
val = [15, 11, 5]
cap = 4
# 动态规划
res = bag(wgt, val, cap)
print(f"不超过背包容量的最大物品价值为 {res}")