Recursion and Dynamic Programming

0/1 Knapsack (Small)

Fill a small 0/1 knapsack table where each row decides whether one more item is available.

Algorithm

Steps

  1. Create a table with one extra row for using zero items.
  2. Process the four items in fixed order.
  3. For each capacity, inherit when the item is too heavy.
  4. Otherwise compare skip and take from the previous row.
  5. Print the best value and the full deterministic table.
state transition `dp[i][w]` compares skipping item `i` with taking it and reading the remaining capacity from the previous row.

Complexity

  • Time: O(item_count * capacity)
  • Space: O(item_count * capacity)

Bash DSA Implementation

basic.sh
Replay: real traced execution (multi-file project)
row_string() {
  local out="["
  local first=1
  for value in "$@"; do
    if (( first )); then first=0; else out+=", "; fi
    out+="$value"
  done
  out+="]"
  printf '%s' "$out"
}

weights=(2 3 4 5)
values=(3 4 5 6)
capacity=5
declare -A dp
for ((item=0; item<=4; item++)); do
  for ((cap=0; cap<=capacity; cap++)); do dp[$item,$cap]=0; done
done
for ((item=1; item<=4; item++)); do
  weight=${weights[item-1]}
  value=${values[item-1]}
  for ((cap=0; cap<=capacity; cap++)); do
    if (( weight > cap )); then
      dp[$item,$cap]=${dp[$((item-1)),$cap]}
    else
      skip=${dp[$((item-1)),$cap]}
      take=$((value + dp[$((item-1)),$((cap-weight))]))
      if (( take > skip )); then dp[$item,$cap]=$take; else dp[$item,$cap]=$skip; fi
    fi
  done
done
echo "${dp[4,5]}"
printf '['
for ((item=0; item<=4; item++)); do
  if (( item > 0 )); then printf ', '; fi
  row=()
  for ((cap=0; cap<=capacity; cap++)); do row+=("${dp[$item,$cap]}"); done
  row_string "${row[@]}"
done
printf ']\n'

  1. row 0 ← [0, 0, 0, 0, 0, 0]

    15declare -A dp16for ((item=0; item<=4; item++)); do17  for ((cap=0; cap<=capacity; cap++)); do dp[$item,$cap]=0; done
    values this step[0, 0, 0, 0, 0, 0]row 0

  2. row 1 ← [0, 0, 3, 3, 3, 3]

    15declare -A dp16for ((item=0; item<=4; item++)); do17  for ((cap=0; cap<=capacity; cap++)); do dp[$item,$cap]=0; done
    values this step[0, 0, 3, 3, 3, 3]row 1

  3. row 2 ← [0, 0, 3, 4, 4, 7]

    15declare -A dp16for ((item=0; item<=4; item++)); do17  for ((cap=0; cap<=capacity; cap++)); do dp[$item,$cap]=0; done
    values this step[0, 0, 3, 4, 4, 7]row 2

  4. row 3 ← [0, 0, 3, 4, 5, 7]

    15declare -A dp16for ((item=0; item<=4; item++)); do17  for ((cap=0; cap<=capacity; cap++)); do dp[$item,$cap]=0; done
    values this step[0, 0, 3, 4, 5, 7]row 3

  5. row 4 ← [0, 0, 3, 4, 5, 7]

    15declare -A dp16for ((item=0; item<=4; item++)); do17  for ((cap=0; cap<=capacity; cap++)); do dp[$item,$cap]=0; done
    values this step[0, 0, 3, 4, 5, 7]row 4

  6. stdout ← 7 [[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]]

    8  out+="]"9  printf '%s' "$out"10}
    values this step7 [[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]]stdout7answer

Output

7
[[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]]