Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Treasures by Moff
from collections import defaultdict
import math
def treasures(safe, limit):
limit = math.floor(limit * 1000)
items = []
for k, v in safe.items():
items.extend([(k, v['weight'], v['price']) for _ in range(min(v['amount'], limit // v['weight']))])
table = [[0] * (limit + 1) for _ in range(len(items) + 1)]
for j in range(1, len(items) + 1):
item, wt, val = items[j - 1]
for w in range(1, limit + 1):
if wt > w:
table[j][w] = table[j - 1][w]
else:
table[j][w] = max(table[j - 1][w], table[j - 1][w - wt] + val)
d = defaultdict(int)
for j in range(len(items), 0, -1):
if table[j][limit] != table[j - 1][limit]:
item, wt, val = items[j - 1]
d[items[j - 1][0]] += 1
limit -= wt
return [f'{k}: {d[k]}' for k in ('golden coin', 'silver coin', 'ruby') if d[k]]
Oct. 7, 2018