Knapsack

Enumerate Subsets

Enumerate every subset in binary mask order. This is a small deterministic example, not solver engineering.

Example

Enumerate every subset in binary mask order.

highlighted = computed this step

Step 1 — Subset

Compute the highlighted combinatorics value.

items, weight, value((empty), 0, 0)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((empty), 0, 0)}}\end{array}

Step 2 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A), 2, 6)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A), 2, 6)}}\end{array}

Step 3 — Subset

Compute the highlighted combinatorics value.

items, weight, value((B), 3, 7)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((B), 3, 7)}}\end{array}

Step 4 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, B), 5, 13)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, B), 5, 13)}}\end{array}

Step 5 — Subset

Compute the highlighted combinatorics value.

items, weight, value((C), 4, 10)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((C), 4, 10)}}\end{array}

Step 6 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, C), 6, 16)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, C), 6, 16)}}\end{array}

Step 7 — Subset

Compute the highlighted combinatorics value.

items, weight, value((B, C), 7, 17)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((B, C), 7, 17)}}\end{array}

Step 8 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, B, C), 9, 23)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, B, C), 9, 23)}}\end{array}

Step 9 — Subset

Compute the highlighted combinatorics value.

items, weight, value((D), 5, 12)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((D), 5, 12)}}\end{array}

Step 10 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, D), 7, 18)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, D), 7, 18)}}\end{array}

Step 11 — Subset

Compute the highlighted combinatorics value.

items, weight, value((B, D), 8, 19)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((B, D), 8, 19)}}\end{array}

Step 12 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, B, D), 10, 25)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, B, D), 10, 25)}}\end{array}

Step 13 — Subset

Compute the highlighted combinatorics value.

items, weight, value((C, D), 9, 22)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((C, D), 9, 22)}}\end{array}

Step 14 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, C, D), 11, 28)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, C, D), 11, 28)}}\end{array}

Step 15 — Subset

Compute the highlighted combinatorics value.

items, weight, value((B, C, D), 12, 29)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((B, C, D), 12, 29)}}\end{array}

Step 16 — Subset

Compute the highlighted combinatorics value.

items, weight, value((A, B, C, D), 14, 35)\begin{array}{c|c}\text{items, weight, value}&\hlmath{\text{((A, B, C, D), 14, 35)}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.