iframe-proxy | Sunbelt Computer Software

History

150 lines (124 loc) · 4.96 KB

Raw

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

"""

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 for i in range(W + 1)] for j 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):

raise ValueError(

"The number of weights must be the "

"same as the number of values.\nBut "

f"got {num_items} weights and {len(val)} values"

)

for i in range(num_items):

if not isinstance(wt[i], int):

raise TypeError(

"All weights must be integers but "

f"got weight of type {type(wt[i])} at index {i}"

)

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 for i in range(w + 1)] for j 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)

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

knapsack.py

Latest commit

History

knapsack.py

File metadata and controls