from collections import namedtuple
from functools import lru_cache
KnapsackItem = namedtuple('KnapsackItem', ('value', 'weight', 'original_item'))
KnapsackResult = namedtuple('KnapsackResult', ('value', 'items'))
def knapsack_with_amount_limit(items, max_weight, max_amount):
"""
Algorithm described at:
https://cs.stackexchange.com/questions/18492/variant-of-the-knapsack-problem
"""
@lru_cache(maxsize=None)
def best_value(idx, rmn_weight, rmn_amt):
"""
Args:
idx: item "human" index (starts from 1)
rmn_weight: remaining weight
rmn_amt: remaining amount
"""
if idx == 0 or rmn_amt == 0:
return KnapsackResult(0, ())
item = items[idx - 1]
# Discard current item if it doesn't fit into weight restriction
if item.weight > rmn_weight:
return best_value(idx - 1, rmn_weight, rmn_amt)
if idx <= rmn_amt:
subresult = best_value(idx - 1, rmn_weight - item.weight, rmn_amt)
return max(
best_value(idx - 1, rmn_weight, rmn_amt),
KnapsackResult(subresult.value + item.value, (*subresult.items, item)),
key=lambda r: r.value)
else:
subresult = best_value(idx - 1, rmn_weight - item.weight, rmn_amt - 1)
return max(
best_value(idx - 1, rmn_weight, rmn_amt),
KnapsackResult(subresult.value + item.value, (*subresult.items, item)),
key=lambda r: r.value)
return best_value(len(items), max_weight, max_amount)