Anonymous user
Knapsack problem/Bounded: Difference between revisions
The previous Python non-zero-one solution is sensitive to the order of the elements in the items list and fails if the first item in the list is not included in the bagged items (e.g. if umbrella is first item)
m (reduced excessive cell widths, indented the table.) |
(The previous Python non-zero-one solution is sensitive to the order of the elements in the items list and fails if the first item in the list is not included in the bagged items (e.g. if umbrella is first item)) |
||
Line 3,375:
sum(item[2] for item in bagged), sum(item[1] for item in bagged)))</lang>
===Non-zero-one solution===
<lang Python>items =
}
keys = list(items.keys())
#cache: could just use memoize module, but explicit caching is clearer
def choose_item(weight, idx, cache):
if idx < 0: return 0, []
k = (weight, idx)
if k in cache: return cache[k]
name, w, v, qty = keys[idx], *items[keys[idx]]
best_v, best_list = 0, []
for i in range(0, qty + 1):
wlim = weight - i * w
if wlim < 0: break
val, taken = choose_item(wlim, idx - 1, cache)
if val + i * v > best_v:
best_v = val + i * v
best_list = taken[:]
best_list.append((i, name))
cache[k] = [best_v, best_list]
return best_v, best_list
v, lst = choose_item(400, len(items) - 1, {})
w = 0
for i,
if
print(*item)
w = w + items[
print
=={{header|R}}==
| |||