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.

Swift DSA Implementation

basic.swift

func rowString(_ row: [Int]) -> String {
    "[" + row.map(String.init).joined(separator: ", ") + "]"
}
func tableString(_ table: [[Int]]) -> String {
    "[" + table.map(rowString).joined(separator: ", ") + "]"
}

let weights = [2, 3, 4, 5]
let values = [3, 4, 5, 6]
let capacity = 5
var dp = Array(repeating: Array(repeating: 0, count: capacity + 1), count: weights.count + 1)
for item in 1...weights.count {
    let weight = weights[item - 1]
    let value = values[item - 1]
    for cap in 0...capacity {
        if weight > cap {
            dp[item][cap] = dp[item - 1][cap]
        } else {
            let skip = dp[item - 1][cap]
            let take = value + dp[item - 1][cap - weight]
            dp[item][cap] = max(skip, take)
        }
    }
}
print(dp[weights.count][capacity])
print(tableString(dp))

Implementation notes

let weights = [2, 3, 4, 5], let values = [3, 4, 5, 6], and let capacity = 5 are immutable Swift inputs for this replay.
var dp = Array(repeating: Array(repeating: 0, count: capacity + 1), count: weights.count + 1) builds a mutable [[Int]] table with five rows and six capacity columns.
Swift Array is a value type with copy-on-write storage, so assignments like dp[item][cap] = ... are written back through the selected row and column.
The outer loop for item in 1...weights.count reserves row 0 for the zero-item base case and maps the current item with weights[item - 1] and values[item - 1].
The inner loop for cap in 0...capacity fills each row left to right.
If weight > cap, the cell copies dp[item - 1][cap]; otherwise it computes skip = dp[item - 1][cap] and take = value + dp[item - 1][cap - weight], then writes max(skip, take).
The trace rows are [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].
print(dp[weights.count][capacity]) writes 7, then tableString(dp) prints the full table in one bracketed line.

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