Skip to content

Commit f331c22

Browse files
itchargeitcharge
committed
Update Pack-ProblemVariants.py
1 parent 7ff6bf9 commit f331c22

1 file changed

Lines changed: 149 additions & 24 deletions

File tree

‎Templates/10.Dynamic-Programming/Pack-ProblemVariants.py‎

Lines changed: 149 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,44 @@
11
class Solution:
2-
3-
# 0-1 背包问题相关变种
2+
# 1. 求恰好装满背包的最大价值
3+
4+
# 0-1 背包问题 求恰好装满背包的最大价值
5+
def zeroOnePackJustFillUp(self, weight: [int], value: [int], W: int):
6+
size = len(weight)
7+
dp = [float('-inf') for _ in range(W + 1)]
8+
dp[0] = 0
9+
10+
# 枚举前 i 种物品
11+
for i in range(1, size + 1):
12+
# 逆序枚举背包装载重量（避免状态值错误）
13+
for w in range(W, weight[i - 1] - 1, -1):
14+
# dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
15+
dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
16+
17+
if dp[W] == float('-inf'):
18+
return -1
19+
return dp[W]
420

5-
# 0-1 背包问题求方案总数
21+
# 完全背包问题 求恰好装满背包的最大价值
22+
def completePackJustFillUp(self, weight: [int], value: [int], W: int):
23+
size = len(weight)
24+
dp = [float('-inf') for _ in range(W + 1)]
25+
dp[0] = 0
26+
27+
# 枚举前 i 种物品
28+
for i in range(1, size + 1):
29+
# 正序枚举背包装载重量
30+
for w in range(weight[i - 1], W + 1):
31+
# dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
32+
dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
33+
34+
if dp[W] == float('-inf'):
35+
return -1
36+
return dp[W]
37+
38+
39+
# 2. 求方案总数
40+
41+
# 0-1 背包问题 求方案总数
642
def zeroOnePackNumbers(self, weight: [int], value: [int], W: int):
743
size = len(weight)
844
dp = [0 for _ in range(W + 1)]
@@ -17,7 +53,25 @@ def zeroOnePackNumbers(self, weight: [int], value: [int], W: int):
1753

1854
return dp[W]
1955

20-
# 0-1 背包问题求最优方案数 思路 1
56+
# 完全背包问题求方案总数
57+
def completePackNumbers(self, weight: [int], value: [int], W: int):
58+
size = len(weight)
59+
dp = [0 for _ in range(W + 1)]
60+
dp[0] = 1
61+
62+
# 枚举前 i 种物品
63+
for i in range(1, size + 1):
64+
# 正序枚举背包装载重量
65+
for w in range(weight[i - 1], W + 1):
66+
# dp[w] = 前 i - 1 种物品装入载重为 w 的背包中的方案数 + 前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品的方案数
67+
dp[w] = dp[w] + dp[w - weight[i - 1]]
68+
69+
return dp[W]
70+
71+
72+
# 3. 求最优方案数
73+
74+
# 0-1 背包问题 求最优方案数 思路 1
2175
def zeroOnePackMaxProfitNumbers1(self, weight: [int], value: [int], W: int):
2276
size = len(weight)
2377
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
@@ -73,25 +127,6 @@ def zeroOnePackMaxProfitNumbers2(self, weight: [int], value: [int], W: int):
73127

74128
return op[W]
75129

76-
77-
# 完全背包问题相关变种
78-
79-
# 完全背包问题求方案总数
80-
def completePackNumbers(self, weight: [int], value: [int], W: int):
81-
size = len(weight)
82-
dp = [0 for _ in range(W + 1)]
83-
dp[0] = 1
84-
85-
# 枚举前 i 种物品
86-
for i in range(1, size + 1):
87-
# 正序枚举背包装载重量
88-
for w in range(weight[i - 1], W + 1):
89-
# dp[w] = 前 i - 1 种物品装入载重为 w 的背包中的方案数 + 前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品的方案数
90-
dp[w] = dp[w] + dp[w - weight[i - 1]]
91-
92-
return dp[W]
93-
94-
95130
# 完全背包问题求最优方案数 思路 1
96131
def completePackMaxProfitNumbers1(self, weight: [int], value: [int], W: int):
97132
size = len(weight)
@@ -146,4 +181,94 @@ def completePackMaxProfitNumbers2(self, weight: [int], value: [int], W: int):
146181
# 方案数 = 不使用第 i - 1 种物品的方案数 + 使用 1 件第 i - 1 种物品的方案数
147182
op[w] = op[w] + op[w - weight[i - 1]]
148183

149-
return dp[size][W]
184+
return dp[size][W]
185+
186+
187+
# 4. 求具体方案
188+
189+
# 0-1 背包问题求具体方案
190+
def zeroOnePackPrintPath(self, weight: [int], value: [int], W: int):
191+
size = len(weight)
192+
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
193+
path = [[False for _ in range(W + 1)] for _ in range(size + 1)]
194+
195+
# 枚举前 i 种物品
196+
for i in range(1, size + 1):
197+
# 枚举背包装载重量
198+
for w in range(W + 1):
199+
# 第 i - 1 件物品装不下
200+
if w < weight[i - 1]:
201+
# dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
202+
dp[i][w] = dp[i - 1][w]
203+
path[i][w] = False
204+
else:
205+
# 选择第 i - 1 件物品获得价值更高
206+
if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
207+
dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
208+
# 取状态转移式第二项：在之前方案基础上添加了第 i - 1 件物品
209+
path[i][w] = True
210+
# 两种方式获得价格相等
211+
elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
212+
dp[i][w] = dp[i - 1][w]
213+
# 取状态转移式第二项：尽量使用第 i - 1 件物品
214+
path[i][w] = True
215+
# 不选择第 i - 1 件物品获得价值最高
216+
else:
217+
dp[i][w] = dp[i - 1][w]
218+
# 取状态转移式第一项：不选择第 i - 1 件物品
219+
path[i][w] = False
220+
221+
res = []
222+
i, w = size, W
223+
while i >= 1 and w >= 0:
224+
if path[i][w]:
225+
res.append(str(i - 1))
226+
w -= weight[i - 1]
227+
i -= 1
228+
229+
return " ".join(res[::-1])
230+
231+
# 0-1 背包问题求具体方案，要求最小序输出
232+
def zeroOnePackPrintPathMinOrder(self, weight: [int], value: [int], W: int):
233+
size = len(weight)
234+
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
235+
path = [[False for _ in range(W + 1)] for _ in range(size + 1)]
236+
237+
weight.reverse()
238+
value.reverse()
239+
240+
# 枚举前 i 种物品
241+
for i in range(1, size + 1):
242+
# 枚举背包装载重量
243+
for w in range(W + 1):
244+
# 第 i - 1 件物品装不下
245+
if w < weight[i - 1]:
246+
# dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
247+
dp[i][w] = dp[i - 1][w]
248+
path[i][w] = False
249+
else:
250+
# 选择第 i - 1 件物品获得价值更高
251+
if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
252+
dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
253+
# 取状态转移式第二项：在之前方案基础上添加了第 i - 1 件物品
254+
path[i][w] = True
255+
# 两种方式获得价格相等
256+
elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
257+
dp[i][w] = dp[i - 1][w]
258+
# 取状态转移式第二项：尽量使用第 i - 1 件物品
259+
path[i][w] = True
260+
# 不选择第 i - 1 件物品获得价值最高
261+
else:
262+
dp[i][w] = dp[i - 1][w]
263+
# 取状态转移式第一项：不选择第 i - 1 件物品
264+
path[i][w] = False
265+
266+
res = []
267+
i, w = size, W
268+
while i >= 1 and w >= 0:
269+
if path[i][w]:
270+
res.append(str(size - i))
271+
w -= weight[i - 1]
272+
i -= 1
273+
274+
return " ".join(res)

0 commit comments

Comments
 (0)