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.

JavaScript DSA Implementation

basic.js 
function rowString(row) { return `[${row.join(", ")}]`; }
function tableString(table) { return `[${table.map(rowString).join(", ")}]`; }
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 5;
const dp = Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(0));
for (let item = 1; item <= weights.length; item++) {
  const weight = weights[item - 1];
  const value = values[item - 1];
  for (let cap = 0; cap <= capacity; cap++) {
    if (weight > cap) dp[item][cap] = dp[item - 1][cap];
    else {
      const skip = dp[item - 1][cap];
      const take = value + dp[item - 1][cap - weight];
      dp[item][cap] = Math.max(skip, take);
    }
  }
}
console.log(dp[weights.length][capacity]);
console.log(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

  • JavaScript stores weights, values, and the DP table as Array objects containing Number values.
  • The table is allocated with Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(0)), so each DP row is a distinct inner array rather than shared by aliasing.
  • The outer loop uses 1-based item rows. The current item is read with weights[item - 1] and values[item - 1], then the inner loop scans capacities 0 through 5.
  • If weight > cap, the cell inherits dp[item - 1][cap]. Otherwise skip and take = value + dp[item - 1][cap - weight] are compared with Math.max(skip, take), using numeric Number arithmetic.
  • The replayed row states are row 0 [0, 0, 0, 0, 0, 0], item 1 [0, 0, 3, 3, 3, 3], item 2 [0, 0, 3, 4, 4, 7], item 3 [0, 0, 3, 4, 5, 7], and item 4 [0, 0, 3, 4, 5, 7].
  • console.log(dp[weights.length][capacity]) prints 7, then tableString(dp) formats the full table. Visible allocation is the input arrays, the outer DP table array, five DP row arrays, the intermediate array from table.map(rowString), and strings created for output; the loops mutate existing table cells.