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

Greedy vs Dynamic Programming: How to Know Which to Apply

📖 Scenario: Imagine you are organizing a small event and need to decide how to allocate your budget to buy snacks. You want to maximize the number of snacks you can buy without exceeding your budget. Sometimes, a simple quick choice works best, but other times you need to think carefully about all options.

🎯 Goal: You will learn how to decide when to use a simple greedy approach and when to use dynamic programming by solving a snack buying problem step-by-step.

📋 What You'll Learn

Create a list of snack prices

Create a budget variable

Write a greedy function to pick snacks quickly

Write a dynamic programming function to pick snacks optimally

Print results of both methods to compare

💡 Why This Matters

🌍 Real World

Choosing items within a budget is common in shopping, resource allocation, and planning tasks.

💼 Career

Understanding when to use greedy or dynamic programming helps in solving optimization problems efficiently in software development and data science.

1

Create the snack prices list

Create a list called snackPrices with these exact values: [2, 3, 1, 4, 6]

DSA Typescript

// Create the snackPrices list with the given values
// Your code here

Hint

Use const snackPrices: number[] = [2, 3, 1, 4, 6]; to create the list.

2

Set the budget variable

Create a variable called budget and set it to 10

DSA Typescript

const snackPrices: number[] = [2, 3, 1, 4, 6];
// Create the budget variable and set it to 10
// Your code here

Hint

Use const budget: number = 10; to set the budget.

3

Write a greedy function to pick snacks quickly

Write a function called greedySnackSelection that takes snackPrices and budget as parameters and returns the maximum number of snacks you can buy by always picking the cheapest snack first without exceeding the budget. Use sorting and a for loop.

DSA Typescript

const snackPrices: number[] = [2, 3, 1, 4, 6];
const budget: number = 10;
// Write the greedySnackSelection function below
// Your code here

Hint

Sort the snack prices from cheapest to expensive. Then pick snacks one by one until the budget is reached.

4

Write a dynamic programming function and print results

Write a function called dpSnackSelection that takes snackPrices and budget and returns the maximum number of snacks you can buy without exceeding the budget using dynamic programming. Then print the results of greedySnackSelection(snackPrices, budget) and dpSnackSelection(snackPrices, budget).

DSA Typescript

const snackPrices: number[] = [2, 3, 1, 4, 6];
const budget: number = 10;

function greedySnackSelection(snackPrices: number[], budget: number): number {
    const sortedPrices = [...snackPrices].sort((a, b) => a - b);
    let count = 0;
    let total = 0;
    for (const price of sortedPrices) {
        if (total + price <= budget) {
            total += price;
            count++;
        } else {
            break;
        }
    }
    return count;
}

// Write the dpSnackSelection function and print results below
// Your code here

Hint

Use a 2D array to store the best number of snacks for each budget and snack count. Then print both results to compare.