Knapsack

Capacity Feasible Filter

Keep only subsets whose weight is at most capacity. This is a small deterministic example, not solver engineering.

Example

Keep only subsets whose weight is at most capacity.

highlighted = computed this step

Step 1 — Capacity

Set up the exact small combinatorics values.

capacity7\begin{array}{c|c}\text{capacity}&\text{7}\end{array}

Step 2 — Feasible rows

Compute the highlighted combinatorics value.

feasible subsets(((empty), 0, 0), ((A), 2, 6), ((B), 3, 7), ((A, B), 5, 13), ((C), 4, 10), ((A, C), 6, 16), ((B, C), 7, 17), ((D), 5, 12), ((A, D), 7, 18))\begin{array}{c|c}\text{feasible subsets}&\hlmath{\text{(((empty), 0, 0), ((A), 2, 6), ((B), 3, 7), ((A, B), 5, 13), ((C), 4, 10), ((A, C), 6, 16), ((B, C), 7, 17), ((D), 5, 12), ((A, D), 7, 18))}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.