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.

Ruby DSA Implementation

basic.rb

def row_string(row)
  "[" + row.join(", ") + "]"
end
def table_string(table)
  "[" + table.map { |row| row_string(row) }.join(", ") + "]"
end

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
dp = Array.new(weights.length + 1) { Array.new(capacity + 1, 0) }
(1..weights.length).each do |item|
  weight = weights[item - 1]
  value = values[item - 1]
  (0..capacity).each do |cap|
    if weight > cap
      dp[item][cap] = dp[item - 1][cap]
    else
      skip = dp[item - 1][cap]
      take = value + dp[item - 1][cap - weight]
      dp[item][cap] = [skip, take].max
    end
  end
end
puts dp[weights.length][capacity]
puts table_string(dp)

Implementation notes

Items are represented by two parallel Ruby arrays: weights = [2, 3, 4, 5] and values = [3, 4, 5, 6].
capacity = 5, so the table has capacity columns 0 through 5.
Array.new(weights.length + 1) { Array.new(capacity + 1, 0) } builds five separate rows of six zeros; the block avoids reusing one row object.
The outer loop uses (1..weights.length).each, so DP row item maps to input index item - 1.
For each item, weight = weights[item - 1] and value = values[item - 1] keep the current pair in local variables.
The inner loop uses (0..capacity).each to fill every capacity in that row.
If weight > cap, the cell inherits dp[item - 1][cap] and avoids reading a negative remaining capacity.
Otherwise skip = dp[item - 1][cap], take = value + dp[item - 1][cap - weight], and [skip, take].max chooses the stored value.
The trace records whole-row states, ending with row 4 as [0, 0, 3, 4, 5, 7].
puts dp[weights.length][capacity] prints 7, then table_string(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]]