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.

Lua DSA Implementation

basic.lua

local function row_string(row)
  local parts = {}
  for i, value in ipairs(row) do parts[i] = tostring(value) end
  return "[" .. table.concat(parts, ", ") .. "]"
end
local function table_string(table_rows)
  local parts = {}
  for i, row in ipairs(table_rows) do parts[i] = row_string(row) end
  return "[" .. table.concat(parts, ", ") .. "]"
end

local weights = {2, 3, 4, 5}
local values = {3, 4, 5, 6}
local capacity = 5
local dp = {}
for item = 1, #weights + 1 do
  dp[item] = {}
  for cap = 1, capacity + 1 do dp[item][cap] = 0 end
end
for item = 1, #weights do
  local weight = weights[item]
  local value = values[item]
  for cap = 0, capacity do
    if weight > cap then
      dp[item + 1][cap + 1] = dp[item][cap + 1]
    else
      local skip = dp[item][cap + 1]
      local take = value + dp[item][cap - weight + 1]
      dp[item + 1][cap + 1] = math.max(skip, take)
    end
  end
end
print(dp[#weights + 1][capacity + 1])
print(table_string(dp))

Implementation notes

The source does not build item records; it uses parallel Lua tables: weights = {2, 3, 4, 5} and values = {3, 4, 5, 6}.
local capacity = 5, so each DP row has six list slots for logical capacities 0 through 5.
Because this Lua code stores rows as 1-based lists, logical capacity cap is stored at column cap + 1.
dp is a table of row tables. The setup loop creates #weights + 1 rows: one row for zero items plus one row after each item.
Every cell starts at 0; the trace shows the zero-item row as [0, 0, 0, 0, 0, 0].
The outer loop is for item = 1, #weights do; each step reads weight = weights[item] and value = values[item].
The inner loop scans capacities forward with for cap = 0, capacity do. This is not the 1D reverse-scan version.
When weight > cap, the code copies from the previous row with dp[item + 1][cap + 1] = dp[item][cap + 1].
Otherwise it compares skip = dp[item][cap + 1] with take = value + dp[item][cap - weight + 1].
math.max(skip, take) writes the best value into the next row, so each item can be used at most once.
The traced rows are: after item 1 (w=2, v=3), [0, 0, 3, 3, 3, 3]; after item 2 (w=3, v=4), [0, 0, 3, 4, 4, 7].
Item 3 (w=4, v=5) updates capacity 4 to 5 but leaves capacity 5 at 7, giving [0, 0, 3, 4, 5, 7].
Item 4 (w=5, v=6) does not beat the existing capacity-5 value, so the final row stays [0, 0, 3, 4, 5, 7].
The final answer is dp[#weights + 1][capacity + 1], which prints 7.
table_string(dp) renders each row with row_string, then joins the rows, matching the printed full table in the replay.

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