@zed1/

knapsack 0-1 weight

Python

No description

fork
loading
Files
  • main.py

This Plugin Crashed!

Error: Error: must not create an existing file {"type":"CREATE_FILE","wid":"0.08549182423888158","path":"main.py","file":{"path":"main.py","content":{"asEncoding":{"base64":"IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiIiIjAtMSBrbmFwc2FjayBwcm9ibGVtOiBPKG4gVykgaW4gdGltZSwgc3BhY2UgYWxnb3JpdGhtIiIiCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IG5hbWVkdHVwbGUKZnJvbSBmdW5jdG9vbHMgaW1wb3J0IGxydV9jYWNoZQoKSXRlbSA9IG5hbWVkdHVwbGUoJ0l0ZW0nLCAndmFsdWUgd2VpZ2h0IGlkJykKCndlaWdodHMgPSAxMTAsIDMwLCAzNCwgNjcsIDMzLCA2NSwgMTksIDgwLCA5OCwgNDUKIyB2YWx1ZSBpcyB3ZWlnaHQgKGluIGdlbmVyYWwsIHRoZSBhbGdvcml0aG0gbWF4aW1pemVzIHZhbHVlKQppdGVtcyA9IFtJdGVtKHcsIHcsIGkpIGZvciBpLCB3IGluIGVudW1lcmF0ZSh3ZWlnaHRzKV0KY2FwYWNpdHkgPSAyMDAgICMgbWF4IHdlaWdodCB3ZSBjYW4gcHV0IGludG8gdGhlIGtuYXBzYWNrCgoKQGxydV9jYWNoZShtYXhzaXplPU5vbmUpICAjIGNhY2hlIGFsbCBjYWxscwpkZWYgYmVzdF92YWx1ZShuaXRlbXMsIHdlaWdodF9saW1pdCk6CiAgICBpZiBuaXRlbXMgPT0gMDogICMgbm8gaXRlbXMKICAgICAgICByZXR1cm4gMCAgIyB6ZXJvIHZhbHVlCiAgICBlbGlmIGl0ZW1zW25pdGVtcyAtIDFdLndlaWdodCA+IHdlaWdodF9saW1pdDoKICAgICAgICAjIG5ldyBpdGVtIGlzIGhlYXZpZXIgdGhhbiB0aGUgY3VycmVudCB3ZWlnaHQgbGltaXQKICAgICAgICByZXR1cm4gYmVzdF92YWx1ZShuaXRlbXMgLSAxLCB3ZWlnaHRfbGltaXQpICAjIGRvbid0IGluY2x1ZGUgbmV3IGl0ZW0KICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIG1heCggICMgbWF4IG9mIHdpdGggYW5kIHdpdGhvdXQgdGhlIG5ldyBpdGVtCiAgICAgICAgICAgIGJlc3RfdmFsdWUobml0ZW1zIC0gMSwgd2VpZ2h0X2xpbWl0KSwgICMgd2l0aG91dAogICAgICAgICAgICBiZXN0X3ZhbHVlKG5pdGVtcyAtIDEsIHdlaWdodF9saW1pdCAtIGl0ZW1zW25pdGVtcyAtIDFdLndlaWdodCkKICAgICAgICAgICAgKyBpdGVtc1tuaXRlbXMgLSAxXS52YWx1ZSkgICMgd2l0aCB0aGUgbmV3IGl0ZW0KCgpyZXN1bHQgPSBbXQp3ZWlnaHRfbGltaXQgPSBjYXBhY2l0eQpmb3IgaSBpbiByZXZlcnNlZChyYW5nZShsZW4oaXRlbXMpKSk6CiAgICBpZiBiZXN0X3ZhbHVlKGkgKyAxLCB3ZWlnaHRfbGltaXQpID4gYmVzdF92YWx1ZShpLCB3ZWlnaHRfbGltaXQpOgogICAgICAgICMgYmV0dGVyIHdpdGggdGhlIGktdGggaXRlbQogICAgICAgIHJlc3VsdC5hcHBlbmQoaXRlbXNbaV0pICAjIGluY2x1ZGUgaXQgaW4gdGhlIHJlc3VsdAogICAgICAgIHdlaWdodF9saW1pdCAtPSBpdGVtc1tpXS53ZWlnaHQKCnByaW50KHJlc3VsdCkKcHJpbnQoJ21heCB3ZWlnaHQnLCBzdW0oeC53ZWlnaHQgZm9yIHggaW4gcmVzdWx0KSkK"},"asBuffer":null},"loaded":true}}
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))