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.

TypeScript DSA Implementation

basic.ts 
function rowString(row: number[]): string { return `[${row.join(", ")}]`; }
function tableString(table: number[][]): string { 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

  • In TypeScript, weights and values are inferred as numeric arrays from their literals, while capacity is the numeric literal 5.
  • The DP table is built with Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(0)). The callback allocates a separate row array for each item count, then fill(0) initializes each capacity slot.
  • The outer loop uses 1-based item rows and reads weights[item - 1] and values[item - 1]; the inner cap loop scans capacities 0 through 5.
  • When weight > cap, the code copies dp[item - 1][cap]. Otherwise it computes skip and take, then writes Math.max(skip, take) into the current row.
  • The trace records row states from row 0 [0, 0, 0, 0, 0, 0] through row 4 [0, 0, 3, 4, 5, 7], with row 2 showing the first combined value 7 at capacity 5.
  • The two console.log calls print 7 and the full table string. Visible allocation is the weights array, values array, nested DP arrays, the table.map(rowString) intermediate array, and the row/table strings; mutation is limited to numeric DP cells.