capacity = capacity + 1 # 初始化背包容量最大值# s, E ?2 l3 z) V
m = np.zeros((n, capacity)) # 初始化9 s4 T5 v7 Z4 A/ r2 f' A; z
x = np.zeros(n)
复制代码
1.v 是一个长度为 n 的列表，表示每个物品的价值。4 U/ b9 |2 L7 b% j$ W
2.w 是一个长度为 n 的列表，表示每个物品的重量。4 a' }' M6 }% b. ~- h
3.n 表示物品的数量。 ; D2 e& N* f1 T4.capacity 表示背包的容量。 n9 p; }$ u r' c2 U$ M6 ~6 P$ n; i' M0 W! _& D( ?! p# ~7 x2 b l. N
代码首先初始化了一个二维数组 m 作为动态规划表，其中 m[j] 表示在考虑前 i 个物品时，背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解，x 表示是否选择第 i 个物品。
for i in range(n): - J8 ]$ v% T! U9 [4 F
for j in range(capacity):! a$ Z/ Z" }6 l' j- R T; o' v
在这个部分，代码使用了一个嵌套的循环，遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j，代码计算了两种情况下的最大总价值：: n# |9 |& l' I: _ \ y, Z
5.如果当前物品的重量 w 小于等于当前容量 j，那么可以选择将第 i 个物品放入背包，此时总价值为 m[i-1][j-w] + v，或者选择不放入，此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m[j]。 8 d' \3 H7 [- U" O6.如果当前物品的重量 w 大于当前容量 j，则无法放入物品，所以总价值等于上一行的值 m[i-1][j]。6 G0 c$ q9 G, p( y) I
( y3 Y. h) V) u, S* ]这个循环填充了动态规划表 m，最终 m[n-1][capacity] 包含了问题的最优解，即在给定容量下可以获得的最大总价值。
capacity = capacity - 1 # p/ i6 S6 _1 {2 r, k
for i in range(n - 1, 0, -1):4 ?2 b: f0 V1 a1 X2 h
if (m[i][capacity] == m[i - 1][capacity]):: p3 a1 _1 Y% T9 o
x[i] = 05 ~: ~8 e- q: R! J% ]
else: % U o& e3 o5 U, c
x[i] = 1 ! v# _/ z- r- P# B3 q" f0 R
capacity -= w[i]( Y0 \ F+ I2 e5 ^$ s q( d$ F
x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码
在这一部分，代码反向遍历动态规划表，从最后一行向前找到解的路径。如果 m[capacity] 等于 m[i-1][capacity]，表示第 i 个物品没有放入背包，否则放入背包，并更新剩余容量 capacity。
