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. Before comparing values, we discard any selection that overloads the knapsack, since an infeasible pack can never be the answer. Filtering to the feasible subsets first narrows the search to legal options only, so the later step can simply pick the most valuable one among them.

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.