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.

Kotlin DSA Implementation

basic.kt 
fun rowString(row: IntArray): String = row.joinToString(prefix = "[", postfix = "]")
fun tableString(table: Array<IntArray>): String = table.joinToString(prefix = "[", postfix = "]") { rowString(it) }

fun main() {
    val weights = intArrayOf(2, 3, 4, 5)
    val values = intArrayOf(3, 4, 5, 6)
    val capacity = 5
    val dp = Array(weights.size + 1) { IntArray(capacity + 1) }
    for (item in 1..weights.size) {
        val weight = weights[item - 1]
        val value = values[item - 1]
        for (cap in 0..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] = maxOf(skip, take)
            }
        }
    }
    println(dp[weights.size][capacity])
    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

  • Kotlin stores weights and values as primitive IntArray values from intArrayOf(2, 3, 4, 5) and intArrayOf(3, 4, 5, 6).
  • val dp = Array(weights.size + 1) { IntArray(capacity + 1) } builds an Array<IntArray> with five independent rows and six zero-initialized cells per row.
  • The dp binding is a val, but table cells mutate in place through dp[item][cap] = ....
  • The outer loop for (item in 1..weights.size) maps DP row item to weights[item - 1] and values[item - 1]; those Int values are copied into local val weight and val value.
  • The inner loop scans capacities with for (cap in 0..capacity). If weight > cap, the cell inherits dp[item - 1][cap].
  • Otherwise the update reads only the previous row: skip = dp[item - 1][cap], take = value + dp[item - 1][cap - weight], then stores maxOf(skip, take).
  • The trace records row states after each item: [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].
  • println(dp[weights.size][capacity]) prints 7, and tableString(dp) formats the full table for the second output line.