bhylu.com

Advertisements

DSA Knapsack Project

A selection result should identify actual items and fit its capacity. Verify those properties independently from the table cell that reports the best value.

Your brief

Reuse the authored 0/1 knapsack implementation on a small original supply list. Translate the returned names back into their records and calculate the selected weight and value separately. The source uses unique item identities so this witness lookup is unambiguous. A real purchasing or safety decision also needs meaningful units, availability and constraints; the invented values here are teaching scores rather than financial recommendations.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as supply-project.py and run python supply-project.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Worked solution

Show the worked solution
supply-project.py
Try in playground

def knapsack(items, capacity):
    if type(capacity) is not int or capacity < 0:
        raise ValueError("Nonnegative integer capacity required")
    if any(not isinstance(name, str) or type(weight) is not int or weight <= 0 or type(value) is not int or value < 0 for name, weight, value in items):
        raise ValueError("Invalid named item")
    if len({name for name, _, _ in items}) != len(items):
        raise ValueError("Unique item names required")
    if (len(items) + 1) * (capacity + 1) > 100000:
        raise ValueError("Teaching table budget exceeded")
    table = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
    for row, (_, weight, value) in enumerate(items, 1):
        for room in range(capacity + 1):
            table[row][room] = table[row - 1][room]
            if weight <= room:
                table[row][room] = max(table[row][room], value + table[row - 1][room - weight])
    chosen, room = [], capacity
    for row in range(len(items), 0, -1):
        if table[row][room] != table[row - 1][room]:
            name, weight, _ = items[row - 1]
            chosen.append(name)
            room -= weight
    return table[-1][capacity], list(reversed(chosen))

items = [("net", 3, 7), ("crate", 2, 4), ("tag", 1, 2)]
value, chosen = knapsack(items, 4)
records = {name: (weight, score) for name, weight, score in items}
weight = sum(records[name][0] for name in chosen)
score = sum(records[name][1] for name in chosen)
assert len(chosen) == len(set(chosen)) and weight <= 4 and score == value
print(chosen)
print(weight, score)

Expected result

['net', 'tag']
4 9

The witnessed subset weighs four and scores nine, agreeing with the solver. Feasibility and score agreement still do not alone prove optimality, so the boundary review compares the returned optimum with exhaustive subsets on small generated cases.

Time, space and assumptions

The solver’s table costs O(nW) time/space. Building the witness lookup and checking selected names adds O(n) expected dictionary work and O(n) storage for these bounded string identities.

Extend and test

Enumerate every subset for a tiny new fixture, compare the best feasible score and verify that the solver never uses one item twice.

Consult the Python 3.12 standard-library reference for container and language contracts; an example result is not a proof of every possible input or real-world performance.

Advertisements