【01背包问题】
问题描述：
给定n个物品和一个容量为capacity的背包，物品i的大小为w[i]，物品i的价值为v[i]。如何选择物品装入背包，使背包中物品价值最大？
思路分析：动态规划
动态规划数组：dp[i][j]表示从前i个物品中挑选物品放入容量为j的背包中所得到的背包的总价值。
则面对第i个物品，有两种选择：放与不放。
①当目前背包容量大于等于当前物品的大小时，可以放，也可以不放，所以要选择两者的最大值。
不放：当前背包的价值和前一个状态（前i-1个物品）相等。所以，dp[i][j] = dp[i-1][j]。 放入：当前背包价值等于前（i-1）个物品判断之后再加上第i个物品的价值。所以，dp[i][j] = dp[i-1][j-w[i]]+v[i]。其中，dp[i-1][j-w[i]]是判断完前（i-1）个物品后的背包内的总价值，加上第i个物品的价值v[i]，即为当前背包价值
②当前背包容量小于当前物品大小时，当前物品一定放不下，所以dp[i][j] = dp[i-1][j]。
状态转移方程为：
j>=w[i]：dp[i][j] = max(dp[i-1][j]，dp[i-1][j-w[i]]+v[i]) j<w[i]：dp[i][j] = dp[i-1][j]代码实现：
①填写动态规划表，dp二维数组初始化为0。
# 填写动态规划表
for i in range(1, n + 1):
for j in range(1, capacity + 1):
# 如果背包容量小于当前物品大小，则不放
if j < w[i]:
dp[i][j] = dp[i - 1][j]
# 反之，可以放也可以不放，取两者的最优解
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
②回溯找到最优解的情况
填完动态规划表之后，能够得到最优解，但是还不知道具体的最优解情况，即要选择哪些物品，所以要回溯找出最优解的组成。
和填写动态规划表相反：
如果dp[i][j] == dp[i-1][j]，说明第i个物品放与不放对背包价值没有影响，所以回到前一状态，即dp[i-1][j]的状态。
如果dp[i][j] ！= dp[i-1][j]且dp[i][j] = dp[i-1][j-w[i]]+v[i]，说明第i个物品放入了背包中，所以回到dp[i-1][j-w[i]]这一状态。
直到i==0，回溯到顶端停止。
在回溯过程中，维护一个res数组，大小为物品的个数，记录对应的物品是否放入背包中。对于放入背包中的物品，数组对应位置的值置为1；没有放入，就置为0。
# 回溯找到最优解情况存放到res数组中，0：不放；1：放
def find(i, j, res):
if i > 0:
# 没有放入第i个物品
if dp[i][j] == dp[i - 1][j]:
# 最优解数组当前位置标记为0
res[i] = 0
# 递归
find(i - 1, j, res)
# 放入第i个物品
elif j - w[i] >= 0 and dp[i][j] == dp[i - 1][j - w[i]] + v[i]:
res[i] = 1
find(i - 1, j - w[i], res)
③完整代码
w = [0, 2, 3, 4, 5] # 物品大小
v = [0, 3, 4, 5, 6] # 每个物品对应的价值
n, capacity = 4, 8
# dp[i][j]表示当前背包容量为j，前i个物品的价值
# 初始化dp数组为0
dp = [[0 for j in range(capacity + 1)] for i in range(n + 1)]
# 存放最优解情况
res= [0 for i in range(n + 1)]
# 填写动态规划表
for i in range(1, n + 1):
for j in range(1, capacity + 1):
# 如果背包容量小于当前物品大小，则不放
if j 0:
# 没有放入第i个物品
if dp[i][j] == dp[i - 1][j]:
# 最优解数组当前位置标记为0
res[i] = 0
# 递归
find(i - 1, j, res)
# 放入第i个物品
elif j - w[i] >= 0 and dp[i][j] == dp[i - 1][j - w[i]] + v[i]:
res[i] = 1
find(i - 1, j - w[i], res)
# 调用回溯函数
find(4, 8, res)
# 输出物品选择情况
print(res)
crystal---
原创文章 88获赞 5访问量 1万+
关注
私信
展开阅读全文
作者：crystal---
