@zed1/

knapsack 0-1 nitems

Python

No description

fork
loading
Files
  • main.py

This Plugin Crashed!

Error: Error: must not create an existing file {"type":"CREATE_FILE","wid":"0.8977690802398051","path":"main.py","file":{"path":"main.py","content":{"asEncoding":{"base64":"IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiIiIjAtMSBrbmFwc2FjayBwcm9ibGVtOiBPKG4gVykgaW4gdGltZSwgc3BhY2UgYWxnb3JpdGhtIiIiCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IG5hbWVkdHVwbGUKZnJvbSBmdW5jdG9vbHMgaW1wb3J0IGxydV9jYWNoZQoKSXRlbSA9IG5hbWVkdHVwbGUoJ0l0ZW0nLCAndmFsdWUgd2VpZ2h0IGlkJykKIyBodHRwczovL3J1LnN0YWNrb3ZlcmZsb3cuY29tL3F1ZXN0aW9ucy84MDc2MDIvJUQwJTkyJUQxJThCJUQxJTg3JUQwJUI4JUQxJTgxJUQwJUJCJUQwJUI1JUQwJUJEJUQwJUI4JUQwJUI1LSVEMCVCQyVEMCVCMCVEMCVCQSVEMSU4MSVEMCVCOCVEMCVCQyVEMCVCMCVEMCVCQiVEMSU4QyVEMCVCRCVEMCVCRSVEMCVCMyVEMCVCRS0lRDAlQkElRDAlQkUlRDAlQkIlRDAlQjglRDElODclRDAlQjUlRDElODElRDElODIlRDAlQjIlRDAlQjAtJUQwJUJCJUQxJThFJUQwJUI0JUQwJUI1JUQwJUI5LSVEMCVCMi0lRDAlQkIlRDAlQjglRDElODQlRDElODIlRDAlQjUKd2VpZ2h0cyA9IDExMCwgMzAsIDM0LCA2NywgMzMsIDY1LCAxOSwgODAsIDk4LCA0NQojIGVhY2ggaXRlbSBzYW1lIHZhbHVlIChpbiBnZW5lcmFsLCB0aGUgYWxnb3JpdGhtIG1heGltaXplcyB2YWx1ZSkgLS0gbWF4aW1pemUgbnVtYmVyIG9mIGl0ZW1zCml0ZW1zID0gW0l0ZW0oMSwgdywgaSkgZm9yIGksIHcgaW4gZW51bWVyYXRlKHdlaWdodHMpXQpjYXBhY2l0eSA9IDIwMCAgIyBtYXggd2VpZ2h0IHdlIGNhbiBwdXQgaW50byB0aGUga25hcHNhY2sKCgpAbHJ1X2NhY2hlKG1heHNpemU9Tm9uZSkgICMgY2FjaGUgYWxsIGNhbGxzCmRlZiBiZXN0X3ZhbHVlKG5pdGVtcywgd2VpZ2h0X2xpbWl0KToKICAgIGlmIG5pdGVtcyA9PSAwOiAgIyBubyBpdGVtcwogICAgICAgIHJldHVybiAwICAjIHplcm8gdmFsdWUKICAgIGVsaWYgaXRlbXNbbml0ZW1zIC0gMV0ud2VpZ2h0ID4gd2VpZ2h0X2xpbWl0OgogICAgICAgICMgbmV3IGl0ZW0gaXMgaGVhdmllciB0aGFuIHRoZSBjdXJyZW50IHdlaWdodCBsaW1pdAogICAgICAgIHJldHVybiBiZXN0X3ZhbHVlKG5pdGVtcyAtIDEsIHdlaWdodF9saW1pdCkgICMgZG9uJ3QgaW5jbHVkZSBuZXcgaXRlbQogICAgZWxzZToKICAgICAgICByZXR1cm4gbWF4KCAgIyBtYXggb2Ygd2l0aCBhbmQgd2l0aG91dCB0aGUgbmV3IGl0ZW0KICAgICAgICAgICAgYmVzdF92YWx1ZShuaXRlbXMgLSAxLCB3ZWlnaHRfbGltaXQpLCAgIyB3aXRob3V0CiAgICAgICAgICAgIGJlc3RfdmFsdWUobml0ZW1zIC0gMSwgd2VpZ2h0X2xpbWl0IC0gaXRlbXNbbml0ZW1zIC0gMV0ud2VpZ2h0KQogICAgICAgICAgICArIGl0ZW1zW25pdGVtcyAtIDFdLnZhbHVlKSAgIyB3aXRoIHRoZSBuZXcgaXRlbQoKCnJlc3VsdCA9IFtdCndlaWdodF9saW1pdCA9IGNhcGFjaXR5CmZvciBpIGluIHJldmVyc2VkKHJhbmdlKGxlbihpdGVtcykpKToKICAgIGlmIGJlc3RfdmFsdWUoaSArIDEsIHdlaWdodF9saW1pdCkgPiBiZXN0X3ZhbHVlKGksIHdlaWdodF9saW1pdCk6CiAgICAgICAgIyBiZXR0ZXIgd2l0aCB0aGUgaS10aCBpdGVtCiAgICAgICAgcmVzdWx0LmFwcGVuZChpdGVtc1tpXSkgICMgaW5jbHVkZSBpdCBpbiB0aGUgcmVzdWx0CiAgICAgICAgd2VpZ2h0X2xpbWl0IC09IGl0ZW1zW2ldLndlaWdodAoKcHJpbnQocmVzdWx0KQpwcmludCgnbml0ZW1zJywgbGVuKHJlc3VsdCkpCg=="},"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')
# 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))