xkcd_knapsack.py

xkcd_knapsack.py

# c.f. https://xkcd.com/287/
from typing import Sequence

target = 1505

weights = [215, 275, 335, 355, 420, 580]

def knapsack(goal: int,                      # what we're trying to add up to
             weights: Sequence[int],         # the weights we can use
             start: int=0,                   # only add weights starting here (prevents duplicate work / answers)
             counts: Sequence[int]=None):    # how many of each we already have

    counts = counts or [0 for _ in weights]  # initialize counts on first call

    if goal == 0:        # counts add up to goal,
        yield counts     # so yield them

    if goal <= 0:        # can't add anymore weights now
        return           # so return

    # For each weight past `start`, add one of it, subtract that from goal,
    # and recurse
    for i, weight in enumerate(weights[start:], start):
        new_counts = [count + 1 if j == i else count
                      for j, count in enumerate(counts)]
        yield from knapsack(goal - weight, weights, i, new_counts)


print(list(knapsack(target, weights)))