0/1 Knapsack (Small)

Fill a small 0/1 knapsack table where each row decides whether one more item is available.

Algorithm

Steps

Create a table with one extra row for using zero items.
Process the four items in fixed order.
For each capacity, inherit when the item is too heavy.
Otherwise compare skip and take from the previous row.
Print the best value and the full deterministic table.

Complexity

Time: O(item_count * capacity)
Space: O(item_count * capacity)

state transition `dp[i][w]` compares skipping item `i` with taking it and reading the remaining capacity from the previous row.

Python DSA Implementation

basic.py

def row_string(row):
    return "[" + ", ".join(str(v) for v in row) + "]"

def table_string(table):
    return "[" + ", ".join(row_string(row) for row in table) + "]"

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]

for item in range(1, len(weights) + 1):
    weight = weights[item - 1]
    value = values[item - 1]
    for cap in range(capacity + 1):
        if weight > cap:
            dp[item][cap] = dp[item - 1][cap]
        else:
            skip = dp[item - 1][cap]
            take = value + dp[item - 1][cap - weight]
            dp[item][cap] = max(skip, take)

print(dp[len(weights)][capacity])
print(table_string(dp))

Output

7
[[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]]

Implementation notes

Python stores the DP table as a list of row lists: [[0] * (capacity + 1) for _ in range(len(weights) + 1)]. The outer list comprehension creates independent rows, avoiding the aliasing pitfall of repeating one nested list.
The loop order is item-first, then capacity. For each item, the code binds weight = weights[item - 1] and value = values[item - 1], then fills dp[item][cap] for every cap from 0 through capacity.
Updates read only from the previous row. If weight > cap, the current cell inherits dp[item - 1][cap]; otherwise Python integers skip and take are compared with max(skip, take) before mutating the current row slot.
The replay-visible states are whole DP rows, ending with [0, 0, 3, 4, 5, 7] for both rows 3 and 4. Allocation is the table rows plus temporary integers and formatting strings, all managed by normal Python GC.