Compute the maximum achievable subset sum not exceeding `capacity` (0/1 subset sum)

knapsack_simple.py

from typing import List, Tuple


def _reconstruct_subset(items: List[int], reachable_history: List[int], target_sum: int) -> List[int]:
    """
    Reconstruct one subset of `items` that achieves `target_sum` using the
    saved DP snapshots in `reachable_history`.
    """
    subset: List[int] = []
    cur_sum = target_sum
    for item, prev_reachable in zip(reversed(items), reversed(reachable_history)):
        if cur_sum >= item and ((prev_reachable >> (cur_sum - item)) & 1):
            subset.append(item)
            cur_sum -= item
            if cur_sum == 0:
                break
    subset.reverse()
    return subset


def subset_sum_at_most(items: List[int], capacity: int) -> Tuple[int, List[int]]:
    """
    Compute the maximum achievable subset sum not exceeding `capacity` (0/1 subset sum).
    Assumes non-negative integers in `items`.
    Returns (best_sum, one_subset_achieving_it).

    Time: O(n * capacity / word_size) via bitset shifts; Space: O(n) snapshots + O(1) bitset.
    """
    # Keep only items within [0, capacity]; larger ones cannot be used.
    filtered = [item for item in items if 0 <= item <= capacity]
    if not filtered:
        return 0, []

    # Sorting is optional; it makes reconstruction deterministic.
    filtered.sort()

    # Bitset DP: reachable[s] == 1 iff sum s is achievable.
    # Bit 0 is initially set (sum 0 is always achievable).
    reachable = 1

    # Mask keeps only bits up to `capacity`.
    BITS_MASK = (1 << (capacity + 1)) - 1

    # Save snapshots of `reachable` before processing each item for reconstruction.
    reachable_history: List[int] = []
    for item in filtered:
        reachable_history.append(reachable)
        reachable = (reachable | ((reachable << item) & BITS_MASK))

    # Best achievable sum <= capacity is the highest set bit (bounded by mask).
    masked = (reachable & BITS_MASK)
    best_sum = masked.bit_length() - 1  # -1 is safe because bit 0 is always set

    subset = _reconstruct_subset(filtered, reachable_history, best_sum)
    return best_sum, subset