0/1 Knapsack (Small)

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

Algorithm

Steps

Create a table with one extra row for using zero items.
Process the four items in fixed order.
For each capacity, inherit when the item is too heavy.
Otherwise compare skip and take from the previous row.
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.

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.