一. 0-1背包问题
给了一些物品的重量和价值，背包只能装下一定重量的物品，求背包能装物品的最大价值（0-1背包问题约定每个物品最多只能用一次）。
w = [5, 4, 7 ,2 ,6] #重量
p = [12,3,10, 3, 6] #价值
v = 12 #包能装下的总重量
n = 5 #物品个数
1）不超过总重量（不要求装满）的情况下，价值最大
w = [5, 4, 7 ,2 ,6] #重量p = [12,3,10, 3, 6] #价值v = 12 #包能装下的总重量n = 5 #物品个数def dynamic1(w, p, v, n):dp = [[0 for i in range(v+1)] for j in range(n+1)] #初始化，dp[i][j]表示: 前i个物品，总重量不超过j的情况下的最大价值for i in range(1, n+1):for j in range(1, v+1):if w[i-1] <= j: #w[i-1]是第i个物品的重量dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + p[i-1]) #装第i个物品or不装第i个物品else:dp[i][j] = dp[i-1][j]return dp[-1][-1]# 对空间复杂度进行优化，由二维数组变成一维def dynamic2(w, p, v, n):dp = [0 for j in range(v+1)]for i in range(1, n+1):for j in range(v, 0, -1): # 从后往前防止dp[j-w[i-1]]被覆盖if j >= w[i-1]:dp[j] = max(dp[j], dp[j-w[i-1]] + p[i-1])#else: dp[j] = dp[j]return dp[-1]
2）要求背包装满的情况下，价值最大
与第一种情况不同的是，这时候的初始化状态需要调整 ，除了dp[i, 0]仍然等于0，其他的dp[i,j]= -inf
这是因为初始状态，背包没有任何物品，只有当背包容量为0时，才可以看作背包被装满了，符合条件，此时价值为0.
def dynamic3(w, p, v, n):dp = [[0 if i == 0 else float('-inf') for i in range(v+1)] for j in range(n+1)] for i in range(1, n+1):for j in range(1, v+1):if w[i-1] <= j: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + p[i-1]) else:dp[i][j] = dp[i-1][j]return dp[-1][-1]# 空间优化def dynamic4(w, p, v, n):dp = [0 if i == 0 else float('-inf') for i in range(v+1)]for i in range(1, n+1):for j in range(v, 0, -1):if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]] + p[i-1]) return dp[-1]
二. 完全背包问题（不限制每个物品的使用次数）
完全背包问题的一种简单实现与与0-1背包问题只有内部的循环次序不同而已。
引用一段话进行解释（链接：/p/7a4e6071bc02）“ 为什么这样 一改就可行呢?首先想想为什么 0-1背包问题中要按照 w=W..0 的逆序来循环。这是因为 要保证第 i 次循环中的状态 f[i][w]是由状态 f[i-1][w-w[i]]递推而来。换句话 说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策 略时，依据的是一个绝无已经选入第 i 件物品的子结果 f[i-1][w-w[i]]。而现 在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物 品”这种策略时，却正需要一个可能已选入第 i 种物品的子结果 f[i][w-w[i]]，所以就可以并且必须采用 w=0..W 的顺序循环。这就是这个简单的程序为何成立的道理。”
def dynamic2(w, p, v, n):dp = [0 for j in range(v+1)]for i in range(1, n+1):for j in range(1, v+1): # 从前往后if j >= w[i-1]:dp[j] = max(dp[j], dp[j-w[i-1]] + p[i-1])#else: dp[j] = dp[j]return dp[-1]
如果觉得《背包问题（0-1背包问题和完全背包问题）》对你有帮助，请点赞、收藏，并留下你的观点哦！
