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)

Visual walkthrough

The pinned items have weights [2, 3, 4, 5], values [3, 4, 5, 6], and capacity 5. The diagrams show each item row, the overweight inherit branch, and the skip-versus-take comparison that produces 7.

Step 1 - Zero items baseline

With no items available, every capacity has value 0.

Row 0: the empty knapsack is worth zero at every capacity.rowcap 0cap 1cap 2cap 3cap 4cap 50 items000000

Step 2 - First item fills a row

Item 1 has weight 2 and value 3, so capacities below 2 inherit 0 and capacities 2 through 5 can take it.

Row 1 after processing item 1 (weight 2, value 3).rowcap 0cap 1cap 2cap 3cap 4cap 5item 1003333choiceinheritinherittaketaketaketake

Step 3 - Overweight capacity inherits

For item 2 (weight 3, value 4) at capacity 2, weight 3 is too large, so the cell inherits skip = 3 from the previous row.

The overweight branch does not read a negative-capacity cell.decisionitemcapskiptakeresultinherit2 (w=3, v=4)23too heavy3row 2 cap 2w > cap2row 1—inherit

Step 4 - Skip or take at capacity 5

At capacity 5 for item 2, skip = 3 while take = 4 + dp[1][2] = 7, so max(skip, take) is 7.

Item 2 improves capacity 5 by taking the item and using the previous row at capacity 2.cellitemcurrent capskip: prev row cap 5take: prev row cap - weight 2resultcompare2 (w=3, v=4)534 + 3 = 77readprevious rowcap 5dp[1][5]dp[1][2] (5 - 3)max

Step 5 - Final processed row reaches value 7

After processing item 4, the final DP row is [0, 0, 3, 4, 5, 7]; item 4 is only the last processed row, not a reconstructed selected-item set.

Complete 0/1 knapsack table for weights [2, 3, 4, 5] and values [3, 4, 5, 6]; the final row means all four items have been processed.rowcap 0cap 1cap 2cap 3cap 4cap 50 items000000item 1003333item 2003447item 3003457item 4 (final processed row)003457

Go DSA Implementation

basic.go 
package main

import (
  "fmt"
  "strings"
)

func rowString(row []int) string {
  parts := make([]string, len(row))
  for i, value := range row {
    parts[i] = fmt.Sprintf("%d", value)
  }
  return "[" + strings.Join(parts, ", ") + "]"
}
func tableString(table [][]int) string {
  parts := make([]string, len(table))
  for i, row := range table {
    parts[i] = rowString(row)
  }
  return "[" + strings.Join(parts, ", ") + "]"
}
func main() {
  weights := []int{2, 3, 4, 5}
  values := []int{3, 4, 5, 6}
  capacity := 5
  dp := make([][]int, len(weights) + 1)
  for i := range dp {
    dp[i] = make([]int, capacity + 1)
  }
  for item := 1; item <= len(weights); item++ {
    weight := weights[item - 1]
    value := values[item - 1]
    for cap := 0; cap <= capacity; cap++ {
      if weight > cap {
        dp[item][cap] = dp[item - 1][cap]
      } else {
        skip := dp[item - 1][cap]
        take := value + dp[item - 1][cap - weight]
        if take > skip { dp[item][cap] = take } else { dp[item][cap] = skip }
      }
    }
  }
  fmt.Println(dp[len(weights)][capacity])
  fmt.Println(tableString(dp))
}

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

Implementation notes

  • Go stores inputs as weights := []int{2, 3, 4, 5} and values := []int{3, 4, 5, 6}, with capacity := 5.
  • The DP table is dp := make([][]int, len(weights)+1), then each row is allocated separately with make([]int, capacity+1). Go zero-values every cell, so row 0 and capacity 0 start as the base cases without an explicit fill.
  • The item loop uses one-based DP rows: for item := 1; item <= len(weights); item++. Each row maps back to the source slices with weight := weights[item-1] and value := values[item-1].
  • The capacity loop scans cap := 0; cap <= capacity; cap++. If weight > cap, the cell inherits dp[item-1][cap]; otherwise it compares skip := dp[item-1][cap] with take := value + dp[item-1][cap-weight].
  • Each cell is written once into the current row, while all reads come from the previous row, preserving 0/1 behavior. The trace records rows: [0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], and [0, 0, 3, 4, 5, 7].
  • fmt.Println(dp[len(weights)][capacity]) prints 7. tableString formats each row with rowString, fmt.Sprintf, and strings.Join, then prints the full nested table.