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. @end @complexity

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

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

SQL DSA Implementation

basic.sql

CREATE TEMP TABLE items(item INTEGER, weight INTEGER, value INTEGER);
INSERT INTO items VALUES (1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6);
CREATE TEMP TABLE caps(cap INTEGER);
INSERT INTO caps VALUES (0), (1), (2), (3), (4), (5);
CREATE TEMP TABLE dp(item INTEGER, cap INTEGER, value INTEGER);
INSERT INTO dp SELECT 0, cap, 0 FROM caps;
INSERT INTO dp
SELECT 1, caps.cap,
       CASE WHEN items.weight > caps.cap THEN prev.value
            ELSE MAX(prev.value, items.value + take_prev.value) END
FROM caps
JOIN items ON items.item = 1
JOIN dp AS prev ON prev.item = 0 AND prev.cap = caps.cap
LEFT JOIN dp AS take_prev ON take_prev.item = 0 AND take_prev.cap = caps.cap - items.weight;
INSERT INTO dp
SELECT 2, caps.cap,
       CASE WHEN items.weight > caps.cap THEN prev.value
            ELSE MAX(prev.value, items.value + take_prev.value) END
FROM caps
JOIN items ON items.item = 2
JOIN dp AS prev ON prev.item = 1 AND prev.cap = caps.cap
LEFT JOIN dp AS take_prev ON take_prev.item = 1 AND take_prev.cap = caps.cap - items.weight;
INSERT INTO dp
SELECT 3, caps.cap,
       CASE WHEN items.weight > caps.cap THEN prev.value
            ELSE MAX(prev.value, items.value + take_prev.value) END
FROM caps
JOIN items ON items.item = 3
JOIN dp AS prev ON prev.item = 2 AND prev.cap = caps.cap
LEFT JOIN dp AS take_prev ON take_prev.item = 2 AND take_prev.cap = caps.cap - items.weight;
INSERT INTO dp
SELECT 4, caps.cap,
       CASE WHEN items.weight > caps.cap THEN prev.value
            ELSE MAX(prev.value, items.value + take_prev.value) END
FROM caps
JOIN items ON items.item = 4
JOIN dp AS prev ON prev.item = 3 AND prev.cap = caps.cap
LEFT JOIN dp AS take_prev ON take_prev.item = 3 AND take_prev.cap = caps.cap - items.weight;
SELECT value FROM dp WHERE item = 4 AND cap = 5;
SELECT '[[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]]';

@end @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]] @end