Dynamic Programming

Knapsack DP Row

Build one 0/1 knapsack row from a previous row and one item. This is a small deterministic dynamic-programming example.

Example

Build one 0/1 knapsack row from a previous row and one item.

highlighted = computed this step

Step 1 — Previous row and item

Compute the highlighted combinatorics value.

previous row, item((0, 0, 6, 7, 7, 13, 13, 13), (C, 4, 10))\begin{array}{c|c}\text{previous row, item}&\hlmath{\text{((0, 0, 6, 7, 7, 13, 13, 13), (C, 4, 10))}}\end{array}

Step 2 — Capacity 0

Compute the highlighted combinatorics value.

capacity, skip, take, best(0, 0, -, 0)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(0, 0, -, 0)}}\end{array}

Step 3 — Capacity 1

Compute the highlighted combinatorics value.

capacity, skip, take, best(1, 0, -, 0)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(1, 0, -, 0)}}\end{array}

Step 4 — Capacity 2

Compute the highlighted combinatorics value.

capacity, skip, take, best(2, 6, -, 6)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(2, 6, -, 6)}}\end{array}

Step 5 — Capacity 3

Compute the highlighted combinatorics value.

capacity, skip, take, best(3, 7, -, 7)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(3, 7, -, 7)}}\end{array}

Step 6 — Capacity 4

Compute the highlighted combinatorics value.

capacity, skip, take, best(4, 7, 10, 10)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(4, 7, 10, 10)}}\end{array}

Step 7 — Capacity 5

Compute the highlighted combinatorics value.

capacity, skip, take, best(5, 13, 10, 13)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(5, 13, 10, 13)}}\end{array}

Step 8 — Capacity 6

Compute the highlighted combinatorics value.

capacity, skip, take, best(6, 13, 16, 16)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(6, 13, 16, 16)}}\end{array}

Step 9 — Capacity 7

Compute the highlighted combinatorics value.

capacity, skip, take, best(7, 13, 17, 17)\begin{array}{c|c}\text{capacity, skip, take, best}&\hlmath{\text{(7, 13, 17, 17)}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.