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.

PHP DSA Implementation

basic.php 
<?php
function row_string($row) { return "[" . implode(", ", $row) . "]"; }
function table_string($table) { return "[" . implode(", ", array_map("row_string", $table)) . "]"; }
$weights = [2, 3, 4, 5];
$values = [3, 4, 5, 6];
$capacity = 5;
$dp = array_fill(0, count($weights) + 1, array_fill(0, $capacity + 1, 0));
for ($item = 1; $item <= count($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];
      $dp[$item][$cap] = max($skip, $take);
    }
  }
}
echo $dp[count($weights)][$capacity] . PHP_EOL;
echo table_string($dp) . PHP_EOL;
?>

Implementation notes

  • The checked PHP inputs are $weights = [2, 3, 4, 5], $values = [3, 4, 5, 6], and $capacity = 5.
  • $dp = array_fill(0, count($weights) + 1, array_fill(0, $capacity + 1, 0)) creates five rows and six capacity columns, all initialized to 0.
  • Row 0 means no items are available; the trace starts it as [0, 0, 0, 0, 0, 0].
  • The outer loop uses $item = 1 through 4; each row reads the matching $weight = $weights[$item - 1] and $value = $values[$item - 1].
  • The inner loop scans $cap = 0 through 5 left to right.
  • If $weight > $cap, the cell inherits $dp[$item - 1][$cap] from the previous row.
  • Otherwise, $skip = $dp[$item - 1][$cap] and $take = $value + $dp[$item - 1][$cap - $weight]; the cell writes max($skip, $take).
  • The trace rows are [0, 0, 3, 3, 3, 3] after item (2,3), [0, 0, 3, 4, 4, 7] after item (3,4), [0, 0, 3, 4, 5, 7] after item (4,5), and unchanged after item (5,6).
  • The best value is $dp[count($weights)][$capacity], which is 7.
  • echo prints 7, then table_string($dp) renders 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]]