-
-
Notifications
You must be signed in to change notification settings - Fork 45.9k
/
knapsack.py
151 lines (125 loc) · 4.97 KB
/
knapsack.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
"""
Given weights and values of n items, put these items in a knapsack of
capacity W to get the maximum total value in the knapsack.
Note that only the integer weights 0-1 knapsack problem is solvable
using dynamic programming.
"""
def mf_knapsack(i, wt, val, j):
"""
This code involves the concept of memory functions. Here we solve the subproblems
which are needed unlike the below example
F is a 2D array with -1s filled up
"""
global f # a global dp table for knapsack
if f[i][j] < 0:
if j < wt[i - 1]:
val = mf_knapsack(i - 1, wt, val, j)
else:
val = max(
mf_knapsack(i - 1, wt, val, j),
mf_knapsack(i - 1, wt, val, j - wt[i - 1]) + val[i - 1],
)
f[i][j] = val
return f[i][j]
def knapsack(w, wt, val, n):
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w_ in range(1, w + 1):
if wt[i - 1] <= w_:
dp[i][w_] = max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]], dp[i - 1][w_])
else:
dp[i][w_] = dp[i - 1][w_]
return dp[n][w_], dp
def knapsack_with_example_solution(w: int, wt: list, val: list):
"""
Solves the integer weights knapsack problem returns one of
the several possible optimal subsets.
Parameters
---------
W: int, the total maximum weight for the given knapsack problem.
wt: list, the vector of weights for all items where wt[i] is the weight
of the i-th item.
val: list, the vector of values for all items where val[i] is the value
of the i-th item
Returns
-------
optimal_val: float, the optimal value for the given knapsack problem
example_optional_set: set, the indices of one of the optimal subsets
which gave rise to the optimal value.
Examples
-------
>>> knapsack_with_example_solution(10, [1, 3, 5, 2], [10, 20, 100, 22])
(142, {2, 3, 4})
>>> knapsack_with_example_solution(6, [4, 3, 2, 3], [3, 2, 4, 4])
(8, {3, 4})
>>> knapsack_with_example_solution(6, [4, 3, 2, 3], [3, 2, 4])
Traceback (most recent call last):
...
ValueError: The number of weights must be the same as the number of values.
But got 4 weights and 3 values
"""
if not (isinstance(wt, (list, tuple)) and isinstance(val, (list, tuple))):
raise ValueError(
"Both the weights and values vectors must be either lists or tuples"
)
num_items = len(wt)
if num_items != len(val):
msg = (
"The number of weights must be the same as the number of values.\n"
f"But got {num_items} weights and {len(val)} values"
)
raise ValueError(msg)
for i in range(num_items):
if not isinstance(wt[i], int):
msg = (
"All weights must be integers but got weight of "
f"type {type(wt[i])} at index {i}"
)
raise TypeError(msg)
optimal_val, dp_table = knapsack(w, wt, val, num_items)
example_optional_set: set = set()
_construct_solution(dp_table, wt, num_items, w, example_optional_set)
return optimal_val, example_optional_set
def _construct_solution(dp: list, wt: list, i: int, j: int, optimal_set: set):
"""
Recursively reconstructs one of the optimal subsets given
a filled DP table and the vector of weights
Parameters
---------
dp: list of list, the table of a solved integer weight dynamic programming problem
wt: list or tuple, the vector of weights of the items
i: int, the index of the item under consideration
j: int, the current possible maximum weight
optimal_set: set, the optimal subset so far. This gets modified by the function.
Returns
-------
None
"""
# for the current item i at a maximum weight j to be part of an optimal subset,
# the optimal value at (i, j) must be greater than the optimal value at (i-1, j).
# where i - 1 means considering only the previous items at the given maximum weight
if i > 0 and j > 0:
if dp[i - 1][j] == dp[i][j]:
_construct_solution(dp, wt, i - 1, j, optimal_set)
else:
optimal_set.add(i)
_construct_solution(dp, wt, i - 1, j - wt[i - 1], optimal_set)
if __name__ == "__main__":
"""
Adding test case for knapsack
"""
val = [3, 2, 4, 4]
wt = [4, 3, 2, 3]
n = 4
w = 6
f = [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
optimal_solution, _ = knapsack(w, wt, val, n)
print(optimal_solution)
print(mf_knapsack(n, wt, val, w)) # switched the n and w
# testing the dynamic programming problem with example
# the optimal subset for the above example are items 3 and 4
optimal_solution, optimal_subset = knapsack_with_example_solution(w, wt, val)
assert optimal_solution == 8
assert optimal_subset == {3, 4}
print("optimal_value = ", optimal_solution)
print("An optimal subset corresponding to the optimal value", optimal_subset)