Knapsack Problem - PackDB Examples

THE PROBLEM

You're packing for a trip with limited luggage space. Each item has a value (how much you need it) and a weight. You want to maximize the total value of what you bring without exceeding a 50-unit weight limit. This is the classic 0/1 knapsack problem — for each item, you either take it (x=1) or leave it (x=0).

SAMPLE DATA

CREATE TABLE Items (
    id INTEGER, name VARCHAR, value INTEGER,
    weight INTEGER, category VARCHAR
);
INSERT INTO Items VALUES
    (1, 'Laptop', 100, 20, 'electronics'),
    (2, 'Mouse', 60, 10, 'electronics'),
    (3, 'Monitor', 120, 30, 'electronics');

THE QUERY

SELECT id, name, value, weight, x as selected
FROM Items
WHERE category = 'electronics'
DECIDE x IS BOOLEAN
SUCH THAT
    SUM(x * weight) <= 50
MAXIMIZE SUM(x * value);

QUERY BREAKDOWN

1

DECIDE x IS BOOLEAN — Creates a binary decision variable x for each row. x=1 means "select this item", x=0 means "skip it".

2

SUM(x * weight) <= 50 — The total weight of selected items must not exceed 50 units.

3

MAXIMIZE SUM(x * value) — Among all valid selections, pick the one with the highest total value.

RESULT

id	name	value	weight	selected
1	Laptop	100	20	1
2	Mouse	60	10	0
3	Monitor	120	30	1

INTERPRETATION

PackDB selected the Laptop (value 100, weight 20) and Monitor (value 120, weight 30) for a total value of 220 and total weight of 50. The Mouse was excluded — including all three would bring the total weight to 60, exceeding the limit. Dropping the Mouse (value 60) loses less value than dropping either the Laptop or Monitor.