Greedy vs DP How to Know Which to Apply in DSA Javascript - Build Both Approaches

Greedy vs DP: How to Know Which to Apply

📖 Scenario: Imagine you are organizing a small event and need to select activities to fill a fixed time slot. Each activity has a duration and a fun score. You want to maximize the total fun score without exceeding the total available time.This project will help you understand when to use a simple greedy approach and when to use dynamic programming (DP) to solve such problems.

🎯 Goal: You will create a list of activities, set a total available time, first try a greedy approach to select activities, then implement a dynamic programming solution to find the best combination. Finally, you will compare the results.

📋 What You'll Learn

Create a list of activities with exact durations and fun scores

Set a total available time variable

Implement a greedy selection based on highest fun per time ratio

Implement a dynamic programming solution to find the maximum fun score within time

Print the results of both approaches

💡 Why This Matters

🌍 Real World

This project models real-life scheduling and resource allocation problems where you must choose the best combination of tasks within limited time or resources.

💼 Career

Understanding when to use greedy algorithms versus dynamic programming is crucial for software engineers solving optimization problems efficiently.

1

Create the list of activities

Create a variable called activities as an array of objects with these exact entries: {name: 'A', duration: 3, fun: 5}, {name: 'B', duration: 2, fun: 3}, {name: 'C', duration: 4, fun: 7}, {name: 'D', duration: 1, fun: 2}

DSA Javascript

// Create the activities array with the given objects
// Your code here

Hint

Use an array with objects. Each object has name, duration, and fun properties.

2

Set the total available time

Create a variable called totalTime and set it to 5

DSA Javascript

const activities = [
  {name: 'A', duration: 3, fun: 5},
  {name: 'B', duration: 2, fun: 3},
  {name: 'C', duration: 4, fun: 7},
  {name: 'D', duration: 1, fun: 2}
];
// Set the total available time to 5
// Your code here

Hint

Just create a number variable named totalTime and assign 5.

3

Implement the greedy selection

Create a function called greedySelection that takes activities and totalTime. Inside, sort activities by descending fun/duration ratio, then select activities in order while total duration does not exceed totalTime. Return an array of selected activity names called greedyResult.

DSA Javascript

const activities = [
  {name: 'A', duration: 3, fun: 5},
  {name: 'B', duration: 2, fun: 3},
  {name: 'C', duration: 4, fun: 7},
  {name: 'D', duration: 1, fun: 2}
];

const totalTime = 5;

// Implement greedySelection function
// Your code here

Hint

Sort by fun/duration ratio descending. Pick activities while total duration is within limit. Return selected names.

4

Implement dynamic programming and print results

Create a function called dpSelection that takes activities and totalTime. Use dynamic programming to find the maximum total fun score without exceeding totalTime. Return an object with maxFun and an array selected of activity names. Then print the results exactly as: console.log('Greedy selection:', greedyResult); and console.log('DP selection:', dpResult.selected, 'with total fun:', dpResult.maxFun);

DSA Javascript

const activities = [
  {name: 'A', duration: 3, fun: 5},
  {name: 'B', duration: 2, fun: 3},
  {name: 'C', duration: 4, fun: 7},
  {name: 'D', duration: 1, fun: 2}
];

const totalTime = 5;

function greedySelection(activities, totalTime) {
  const sorted = activities.slice().sort((a, b) => (b.fun / b.duration) - (a.fun / a.duration));
  let timeUsed = 0;
  const selected = [];
  for (const activity of sorted) {
    if (timeUsed + activity.duration <= totalTime) {
      selected.push(activity.name);
      timeUsed += activity.duration;
    }
  }
  return selected;
}

const greedyResult = greedySelection(activities, totalTime);

// Implement dpSelection function and print results
// Your code here

Hint

Use a 2D array for DP table. Track max fun for each activity and time. Backtrack to find selected activities. Print results exactly as instructed.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem needs to store results of subproblems

B. When the problem requires checking all possible solutions

C. When overlapping subproblems are present

D. When the problem has the greedy choice property and optimal substructure

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum, known as the greedy choice property.

2. Step 2: Compare with dynamic programming conditions

   Dynamic programming is used when problems have overlapping subproblems and optimal substructure, but greedy algorithms require only the greedy choice property and optimal substructure.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option D

4. Quick Check:

   Greedy choice property = Use greedy [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems as greedy condition
• Using dynamic programming when greedy suffices
• Ignoring greedy choice property

2. Which syntax correctly initializes a memoization array for dynamic programming in JavaScript?

easy

A. const memo = new Array(n).fill(-1);

B. const memo = Array(n).map(() => 0);

C. const memo = new Array(n).map(() => 0);

D. const memo = Array.fill(n, -1);

Solution

1. Step 1: Understand Array initialization

   Using new Array(n).fill(-1) creates an array of length n filled with -1, suitable for memoization since -1 indicates uncomputed.

2. Step 2: Check other options

   A and C fill with 0, which conflicts if 0 is a valid result; map is also unnecessary. D is invalid syntax.

3. Final Answer:

   const memo = new Array(n).fill(-1); -> Option A

4. Quick Check:

   Use new Array(n).fill(value) for memo [OK]

Hint: Use new Array(n).fill(value) to initialize arrays [OK]

Common Mistakes:

• Using map on uninitialized array
• Wrong order of fill arguments
• Using Array.fill which is invalid

3. What is the output of the following JavaScript code?

function maxSum(arr) {
  let incl = arr[0];
  let excl = 0;
  for (let i = 1; i < arr.length; i++) {
    let new_excl = Math.max(incl, excl);
    incl = excl + arr[i];
    excl = new_excl;
  }
  return Math.max(incl, excl);
}
console.log(maxSum([3, 2, 7, 10]));

medium

A. 17

B. 13

C. 20

D. 22

Solution

1. Step 1: Trace variables for each element

   Start: incl=3, excl=0 i=1: new_excl=max(3,0)=3; incl=0+2=2; excl=3 i=2: new_excl=max(2,3)=3; incl=3+7=10; excl=3 i=3: new_excl=max(10,3)=10; incl=3+10=13; excl=10

2. Step 2: Calculate final max

   Return max(incl, excl) = max(13, 10) = 13

3. Final Answer:

   17 -> Option A

4. Quick Check:

   Max sum non-adjacent = 17 [OK]

Hint: Track incl and excl sums carefully [OK]

Common Mistakes:

• Adding adjacent elements mistakenly
• Mixing incl and excl updates
• Misreading problem as max sum of all elements

4. Identify the error in this greedy algorithm code for coin change problem and fix it:

function coinChange(coins, amount) {
  coins.sort();
  let count = 0;
  for (let i = 0; i < coins.length; i++) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return amount === 0 ? count : -1;
}
console.log(coinChange([1, 3, 4], 6));

medium

A. Return count without checking amount

B. Change while loop to if condition

C. Sort coins in descending order using coins.sort((a,b) => b - a)

D. Use recursion instead of loop

Solution

1. Step 1: Check sorting order

   coins.sort() sorts ascending (smallest first), but loop from i=0 processes small coins first, not greedy.

2. Step 2: Fix sorting for greedy approach

   Use coins.sort((a,b) => b - a) to sort descending numerically, so largest coins used first.

3. Final Answer:

   Sort coins in descending order using coins.sort((a,b) => b - a) -> Option C

4. Quick Check:

   Correct numeric descending sort fixes greedy coin change [OK]

Hint: Sort coins descending numerically for greedy coin change [OK]

Common Mistakes:

• Using default sort causing wrong order
• Changing loop logic unnecessarily
• Ignoring amount check in return

5. Given a set of tasks with start and end times, which approach is best to find the maximum number of non-overlapping tasks?

const tasks = [
  {start: 1, end: 3},
  {start: 2, end: 5},
  {start: 4, end: 7},
  {start: 6, end: 9}
];

Choose the best method to solve this scheduling problem.

hard

A. Use recursion without memoization

B. Use a greedy algorithm by sorting tasks by earliest end time

C. Use dynamic programming to check all subsets of tasks

D. Sort tasks by start time and pick the longest tasks first

Solution

1. Step 1: Understand problem type

   This is the classic activity selection problem, where we want the maximum number of non-overlapping intervals.

2. Step 2: Identify best approach

   Greedy algorithm works best by sorting tasks by earliest end time and selecting tasks that start after the last selected task ends.

3. Final Answer:

   Use a greedy algorithm by sorting tasks by earliest end time -> Option B

4. Quick Check:

   Greedy by earliest end time solves scheduling [OK]

Hint: Sort by end time, pick earliest finishing tasks [OK]

Common Mistakes:

• Trying all subsets with DP unnecessarily
• Sorting by start time instead of end time
• Picking longest tasks first causes overlaps