-
Notifications
You must be signed in to change notification settings - Fork 9
Expand file tree
/
Copy pathknapsack.py
More file actions
40 lines (34 loc) · 1.3 KB
/
knapsack.py
File metadata and controls
40 lines (34 loc) · 1.3 KB
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
def knapsack(items, maxweight):
"""
Solve the knapsack problem by finding the most valuable
subsequence of `items` subject that weighs no more than
`maxweight`.
`items` is a sequence of pairs `(value, weight)`, where `value` is
a number and `weight` is a non-negative integer.
`maxweight` is a non-negative integer.
Return a pair whose first element is the sum of values in the most
valuable subsequence, and whose second element is the subsequence.
>>> items = [(4, 12), (2, 1), (6, 4), (1, 1), (2, 2)]
>>> knapsack(items, 15)
(11, [(2, 1), (6, 4), (1, 1), (2, 2)])
"""
# Return the value of the most valuable subsequence of the first i
# elements in items whose weights sum to no more than j.
@memoized
def bestvalue(i, j):
if i == 0:
return 0
value, weight = items[i - 1]
if weight > j:
return bestvalue(i - 1, j)
else:
return max(bestvalue(i - 1, j),
bestvalue(i - 1, j - weight) + value)
j = maxweight
result = []
for i in xrange(len(items), 0, -1):
if bestvalue(i, j) != bestvalue(i - 1, j):
result.append(items[i - 1])
j -= items[i - 1][1]
result.reverse()
return bestvalue(len(items), maxweight), result