@zed1/

# knapsack 0-1 weight

## No description

Files
• main.py
main.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
```
```#!/usr/bin/env python
"""0-1 knapsack problem: O(n W) in time, space algorithm"""
from collections import namedtuple
from functools import lru_cache

Item = namedtuple('Item', 'value weight id')

weights = 110, 30, 34, 67, 33, 65, 19, 80, 98, 45
# value is weight (in general, the algorithm maximizes value)
items = [Item(w, w, i) for i, w in enumerate(weights)]
capacity = 200  # max weight we can put into the knapsack

@lru_cache(maxsize=None)  # cache all calls
def best_value(nitems, weight_limit):
if nitems == 0:  # no items
return 0  # zero value
elif items[nitems - 1].weight > weight_limit:
# new item is heavier than the current weight limit
return best_value(nitems - 1, weight_limit)  # don't include new item
else:
return max(  # max of with and without the new item
best_value(nitems - 1, weight_limit),  # without
best_value(nitems - 1, weight_limit - items[nitems - 1].weight)
+ items[nitems - 1].value)  # with the new item

result = []
weight_limit = capacity
for i in reversed(range(len(items))):
if best_value(i + 1, weight_limit) > best_value(i, weight_limit):
# better with the i-th item
result.append(items[i])  # include it in the result
weight_limit -= items[i].weight

print(result)
print('max weight', sum(x.weight for x in result))
```