repl.it
@zed1/

knapsack 0-1 nitems

Python

No description

fork
loading
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')
# https://ru.stackoverflow.com/questions/807602/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5-%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE-%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%B0-%D0%BB%D1%8E%D0%B4%D0%B5%D0%B9-%D0%B2-%D0%BB%D0%B8%D1%84%D1%82%D0%B5
weights = 110, 30, 34, 67, 33, 65, 19, 80, 98, 45
# each item same value (in general, the algorithm maximizes value) -- maximize number of items
items = [Item(1, 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('nitems', len(result))