DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Build Both Approaches

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: Imagine you are helping a delivery company decide the best way to pack boxes with items to maximize value without exceeding weight limits. You will explore three ways to solve this: simple recursion, greedy choice, and dynamic programming.

🎯 Goal: You will create a list of items with weights and values, set a maximum weight limit, then write code to find the best total value using recursion, greedy, and dynamic programming approaches. Finally, you will print the results to compare.

📋 What You'll Learn

Create a list of items with exact weights and values

Set a maximum weight limit variable

Write a recursive function to find max value without exceeding weight

Write a greedy function that picks items by value-to-weight ratio

Write a dynamic programming function to find max value efficiently

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Packing delivery boxes or loading cargo efficiently to maximize value without exceeding weight limits.

💼 Career

Understanding when to use recursion, greedy algorithms, or dynamic programming is key for software engineers solving optimization problems.

1

Create the list of items

Create a variable called items as an array of objects with these exact entries: { weight: 2, value: 3 }, { weight: 3, value: 4 }, { weight: 4, value: 5 }, and { weight: 5, value: 8 }.

DSA Typescript

// Your code here

Hint

Use const items = [ ... ] with objects inside.

2

Set the maximum weight limit

Create a variable called maxWeight and set it to 8.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];
// Your code here

Hint

Use const maxWeight = 8; to set the limit.

3

Write the recursive function to find max value

Write a function called knapsackRecursive that takes index and remainingWeight as parameters and returns the maximum value. Use recursion to decide whether to include or exclude the current item at items[index]. If index is out of range or remainingWeight is zero or less, return 0.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];

const maxWeight = 8;

// Your code here

Hint

Use recursion with base case when index is beyond last item or no weight left.

4

Print the results of all methods

Write three lines to print the results of calling knapsackRecursive(0, maxWeight), knapsackGreedy(), and knapsackDP(). Use console.log with labels: "Recursive:", "Greedy:", and "DP:" respectively.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];

const maxWeight = 8;

function knapsackRecursive(index: number, remainingWeight: number): number {
  if (index >= items.length || remainingWeight  remainingWeight) {
    return knapsackRecursive(index + 1, remainingWeight);
  } else {
    const include = items[index].value + knapsackRecursive(index + 1, remainingWeight - items[index].weight);
    const exclude = knapsackRecursive(index + 1, remainingWeight);
    return Math.max(include, exclude);
  }
}

function knapsackGreedy(): number {
  const sortedItems = [...items].sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let totalWeight = 0;
  let totalValue = 0;
  for (const item of sortedItems) {
    if (totalWeight + item.weight  Array(maxWeight + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= maxWeight; w++) {
      if (items[i - 1].weight <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - items[i - 1].weight] + items[i - 1].value);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][maxWeight];
}

// Your code here

Hint

Use console.log("Recursive:", knapsackRecursive(0, maxWeight)) and similar for greedy and DP.