test knapsack, basic dynamic programing problem

t_pack.py

import random
import functools


def pack_prestore(ws, avail, vs=None):
    """
    ws: weight list, integer
    vs: value list; if None, reduced to subset sum problem
    use cache to pre store recursive value
    return optimal value
    """
    cache = {}  # {(i, w): optimal}
    # i: subset from {0,...i}
    # w: space available(max allowed)
    n = len(ws)
    for i in range(-1, n):
        # assume discrete capacities
        for w in range(0, avail + 1):
            if i < 0:
                cache[(i, w)] = 0
            elif w < ws[i]:
                cache[(i, w)] = cache[(i - 1), w]
            else:
                # packing problem or subset problem
                v = vs and vs[i] or ws[i]
                cache[(i, w)] = max(cache[(i - 1, w)],
                                    cache[(i - 1, w - ws[i])] + v)
    return cache[(n - 1, avail)]


def pack_recursive(ws, avail, vs=None):
    @functools.cache
    def calc(i, w):
        if i < 0:
            return 0
        if ws[i] > w:
            return calc(i - 1, w)
        else:
            # packing problem or subset problem
            v = vs and vs[i] or ws[i]
            return max(calc(i - 1, w),
                       calc(i - 1, w - ws[i]) + v)

    opt = calc(len(ws) - 1, avail)
    print(calc.cache_info())
    return opt


# how to test efficiently:
def test_pack(pack_fn, ws, avail, vs=None):
    opt = pack_fn(ws, avail)
    print(
        f"fn: {pack_fn.__name__}, ws: {ws}, vs: {vs}, avail: {avail}, opt: {opt}"
    )
    return opt


def test_case(ws, avail, vs=None):
    last = None
    for fn in (pack_prestore, pack_recursive):
        for ws_ in (ws, sorted(ws, reverse=True)):
            res = test_pack(fn, tuple(ws_), avail)
        if last:
            assert last == res, f"{fn.__name__}, {ws}, {res} != {last}"
        last = res


def test():
    for (ws, avail) in (
        ((2, 2, 3), 6),
        ([random.randint(1, 100) for _ in range(10)], 50),
    ):
        test_case(ws, avail)


def test_random(fn):
    random.seed(555)
    N = 10
    capacity = int(N * 100 / 5)
    print(f"N: {N}, capacity: {capacity}")
    # [(weight, value)] to shuffle together
    wvs = [(1.0 + random.random() * 99, 1.0 + random.random() * 500) for _ in range(N)]
    last = None
    n = 10  # shuffle times
    for i in range(n):
        if i < n - 2:
            random.shuffle(wvs)
        else:
            # sorted order by ws
            reverse = (i == n - 1)
            wvs = sorted(wvs, reverse=reverse, key=lambda kv: kv[0])
            print(f"{wvs}: reverse: {reverse}")
        ws, vs = list(zip(*wvs))
        optimal = fn(ws, capacity, vs)
        if last:
            assert round(last, 6) == round(optimal, 6), f"{fn.__name__}, ws: {ws}, vs: {vs}, {optimal} != {last}"
        last = optimal


if __name__ == "__main__":
    # test()
    test_random(pack_recursive)