0/1 knapsack, subset sum and partition

"""Choosing features for a sprint of 10 working days: a 0/1 knapsack, filled as a table and walked back."""
from itertools import combinations

CAPACITY = 10  # working days in the sprint
features = [  # (name, days of work, value to users)
    ("onboarding tour", 1, 6),
    ("dark mode", 2, 15),
    ("CSV export", 3, 24),
    ("two-factor login", 5, 50),
    ("search filters", 5, 50),
    ("audit log", 6, 66),
]


def table(items, capacity):
    """best[i][w]: the most value from the first i items within w days."""
    best = [[0] * (capacity + 1)]
    for _, days, value in items:
        above = best[-1]
        row = list(above)  # leaving the item out keeps the row above
        for w in range(days, capacity + 1):
            row[w] = max(above[w], above[w - days] + value)
        best.append(row)
    return best


def walk_back(items, best, capacity):
    chosen, w = [], capacity
    for i in range(len(items), 0, -1):
        if best[i][w] != best[i - 1][w]:  # the item made the difference, so it was packed
            name, days, _ = items[i - 1]
            chosen.append(name)
            w -= days
    return chosen[::-1]


best = table(features, CAPACITY)
print("days:              " + " ".join(f"{w:>3}" for w in range(CAPACITY + 1)))
print("no features:       " + " ".join(f"{x:>3}" for x in best[0]))
for (name, days, value), row in zip(features, best[1:]):
    print(f"+ {name:<16} " + " ".join(f"{x:>3}" for x in row))
print(f"best value {best[-1][-1]}: {walk_back(features, best, CAPACITY)}")

ratio = sorted(features, key=lambda f: f[2] / f[1], reverse=True)
left, value, picked = CAPACITY, 0, []
for name, days, v in ratio:
    if days <= left:
        left, value, picked = left - days, value + v, picked + [name]
print(f"best value per day first: {value}: {picked}")

top = max(
    (sum(v for _, _, v in c), [n for n, _, _ in c])
    for r in range(len(features) + 1)
    for c in combinations(features, r)
    if sum(d for _, d, _ in c) <= CAPACITY
)
print(f"every one of the {2 ** len(features)} subsets tried: {top[0]}: {top[1]}")

days:                0   1   2   3   4   5   6   7   8   9  10
no features:         0   0   0   0   0   0   0   0   0   0   0
+ onboarding tour    0   6   6   6   6   6   6   6   6   6   6
+ dark mode          0   6  15  21  21  21  21  21  21  21  21
+ CSV export         0   6  15  24  30  39  45  45  45  45  45
+ two-factor login   0   6  15  24  30  50  56  65  74  80  89
+ search filters     0   6  15  24  30  50  56  65  74  80 100
+ audit log          0   6  15  24  30  50  66  72  81  90 100
best value 100: ['two-factor login', 'search filters']
best value per day first: 96: ['audit log', 'CSV export', 'onboarding tour']
every one of the 64 subsets tried: 100: ['two-factor login', 'search filters']

"""The sprint table in one row: capacities looped downwards, then upwards by mistake."""
import random

CAPACITY = 10
features = [("onboarding tour", 1, 6), ("dark mode", 2, 15), ("CSV export", 3, 24),
            ("two-factor login", 5, 50), ("search filters", 5, 50), ("audit log", 6, 66)]


def one_row(items, capacity, downwards=True):
    dp = [0] * (capacity + 1)  # dp[w]: the most value within w days, for the items seen so far
    for _, days, value in items:
        ws = range(capacity, days - 1, -1) if downwards else range(days, capacity + 1)
        for w in ws:
            dp[w] = max(dp[w], dp[w - days] + value)
    return dp


print(f"after the tour, downwards: {one_row(features[:1], CAPACITY)}")
print(f"after the tour, upwards:   {one_row(features[:1], CAPACITY, downwards=False)}")
print(f"all six, downwards: {one_row(features, CAPACITY)}")
print(f"all six, upwards:   {one_row(features, CAPACITY, downwards=False)}")

rng = random.Random(14)
differ = 0
for _ in range(1_000):
    items = [("", rng.randint(1, 8), rng.randint(1, 60)) for _ in range(rng.randint(1, 8))]
    differ += one_row(items, 20)[-1] != one_row(items, 20, downwards=False)[-1]
print(f"1,000 random lists, capacity 20: the upward loop changed the answer {differ} times")

after the tour, downwards: [0, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
after the tour, upwards:   [0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60]
all six, downwards: [0, 6, 15, 24, 30, 50, 66, 72, 81, 90, 100]
all six, upwards:   [0, 6, 15, 24, 30, 50, 66, 72, 81, 90, 100]
1,000 random lists, capacity 20: the upward loop changed the answer 1000 times

"""Subset sum and equal partition: the same table with True and False instead of values."""


def reachable(numbers, limit):
    """can[t] is True when some subset of the numbers adds up to exactly t (t from 0 to limit)."""
    can = [True] + [False] * limit  # the empty subset makes 0
    for x in numbers:
        for t in range(limit, x - 1, -1):  # downwards, so each number is used at most once
            if can[t - x]:
                can[t] = True
    return can


def equal_split(numbers):
    """One group with half the total, or None; the other group is everything else."""
    total = sum(numbers)
    if total % 2:
        return None
    half = total // 2
    # rows[i][t]: some subset of the first i numbers adds up to t
    rows = [[True] + [False] * half]
    for x in numbers:
        above = rows[-1]
        rows.append([above[t] or (t >= x and above[t - x]) for t in range(half + 1)])
    if not rows[-1][half]:
        return None
    group, t = [], half
    for i in range(len(numbers), 0, -1):
        if not rows[i - 1][t]:  # t was not reachable without number i, so number i is in the group
            group.append(numbers[i - 1])
            t -= numbers[i - 1]
    return group[::-1]


payments = [7, 11, 3, 19, 5]
can = reachable(payments, 45)
print(f"totals that some of {payments} make: {[t for t in range(46) if can[t]]}")
print(f"26 reachable: {can[26]}; 2 reachable: {can[2]}")
parcels = [8, 6, 5, 7, 3, 9, 4]
group = equal_split(parcels)
print(f"parcels {parcels}, total {sum(parcels)}: one rider takes {group}, the other the rest, {sum(group)} kg each")
print(f"parcels [8, 6, 5, 3]: {equal_split([8, 6, 5, 3])}")

totals that some of [7, 11, 3, 19, 5] make: [0, 3, 5, 7, 8, 10, 11, 12, 14, 15, 16, 18, 19, 21, 22, 23, 24, 26, 27, 29, 30, 31, 33, 34, 35, 37, 38, 40, 42, 45]
26 reachable: True; 2 reachable: False
parcels [8, 6, 5, 7, 3, 9, 4], total 42: one rider takes [8, 6, 7], the other the rest, 21 kg each
parcels [8, 6, 5, 3]: [6, 5]