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.

Complexity

  • Time: O(item_count * capacity)
  • Space: O(item_count * capacity)
state transition `dp[i][w]` compares skipping item `i` with taking it and reading the remaining capacity from the previous row.

Scala DSA Implementation

basic.scala 
object Main extends App {
  def rowString(row: Array[Int]): String = row.mkString("[", ", ", "]")
  def tableString(table: Array[Array[Int]]): String = table.map(rowString).mkString("[", ", ", "]")
  val weights = Array(2, 3, 4, 5)
  val values = Array(3, 4, 5, 6)
  val capacity = 5
  val dp = Array.fill(weights.length + 1, capacity + 1)(0)
  for (item <- 1 to weights.length) {
    val weight = weights(item - 1)
    val value = values(item - 1)
    for (cap <- 0 to capacity) {
      if (weight > cap) dp(item)(cap) = dp(item - 1)(cap)
      else {
        val skip = dp(item - 1)(cap)
        val take = value + dp(item - 1)(cap - weight)
        dp(item)(cap) = math.max(skip, take)
      }
    }
  }
  println(dp(weights.length)(capacity))
  println(tableString(dp))
}

Implementation notes

  • weights and values are parallel Scala Array[Int] values: weights 2, 3, 4, 5 pair with values 3, 4, 5, 6.
  • val dp = Array.fill(weights.length + 1, capacity + 1)(0) allocates a 5-by-6 table for rows 0..4 and capacities 0..5.
  • The val dp reference stays fixed, but cells are mutable through dp(item)(cap) = ....
  • The outer loop is item-first: for (item <- 1 to weights.length), with weights(item - 1) and values(item - 1) mapping the 1-based DP row to the 0-based input arrays.
  • The inner loop scans every capacity with for (cap <- 0 to capacity).
  • If weight > cap, the row inherits dp(item - 1)(cap) without reading a negative remaining capacity.
  • Otherwise it computes skip = dp(item - 1)(cap) and take = value + dp(item - 1)(cap - weight), then writes math.max(skip, take).
  • The trace records whole-row transitions, ending with row 4 as [0, 0, 3, 4, 5, 7].
  • println(dp(weights.length)(capacity)) prints the final answer 7, then tableString(dp) prints the full table.

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]]