Greedy vs DP How to Know Which to Apply in DSA C# - 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 maximize fun within a limited time. Some activities can be chosen partially, while others must be chosen fully or not at all. You want to learn how to decide when to use a simple greedy approach or a more careful dynamic programming method.

🎯 Goal: You will create a list of activities with their durations and fun values, set a total available time, then write code to select activities using a greedy approach and a dynamic programming approach. Finally, you will print the total fun value from each method to compare results.

📋 What You'll Learn

Create a list of activities with exact durations and fun values

Set a total available time as an integer variable

Implement a greedy selection based on fun per unit time

Implement a dynamic programming solution for exact selection

Print the total fun values from both methods

💡 Why This Matters

🌍 Real World

Choosing activities or tasks to maximize benefit within limited resources is common in event planning, budgeting, and scheduling.

💼 Career

Understanding when to use greedy algorithms versus dynamic programming helps software engineers optimize solutions for resource allocation, scheduling, and decision-making problems.

1

Create the list of activities

Create a list of tuples called activities with these exact entries: (2, 10), (3, 14), (1, 7), (4, 20), (2, 8). Each tuple represents (duration, fun).

DSA C#

# Create the list of activities with exact tuples
# Your code here

Hint

Use List<(int, int)> and add the exact tuples inside curly braces.

2

Set the total available time

Add an integer variable called totalTime and set it to 7.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List activities = new List
        {
            (2, 10),
            (3, 14),
            (1, 7),
            (4, 20),
            (2, 8)
        };
        // Set total available time
        // Your code here
    }
}

Hint

Declare int totalTime = 7; inside the Main method.

3

Implement the greedy selection

Write code to sort activities by descending fun per duration ratio, then select activities greedily until totalTime is used up or no more activities fit. Store the sum of fun values in an integer variable called greedyFun.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List activities = new List
        {
            (2, 10),
            (3, 14),
            (1, 7),
            (4, 20),
            (2, 8)
        };
        int totalTime = 7;
        // Sort activities by fun per duration descending
        // Select activities greedily until totalTime is used
        // Store sum of fun in greedyFun
        // Your code here
    }
}

Hint

Sort using OrderByDescending on fun/duration, then loop and add activities if they fit.

4

Implement dynamic programming and print results

Implement a dynamic programming solution to find the maximum fun value achievable within totalTime using the activities exactly (0/1 knapsack). Store the result in an integer variable called dpFun. Then print both greedyFun and dpFun on separate lines.

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List activities = new List
        {
            (2, 10),
            (3, 14),
            (1, 7),
            (4, 20),
            (2, 8)
        };
        int totalTime = 7;

        var sortedActivities = activities.OrderByDescending(a => (double)a.fun / a.duration).ToList();
        int timeUsed = 0;
        int greedyFun = 0;

        foreach (var activity in sortedActivities)
        {
            if (timeUsed + activity.duration <= totalTime)
            {
                timeUsed += activity.duration;
                greedyFun += activity.fun;
            }
        }

        // Implement DP solution to find max fun
        // Print greedyFun and dpFun
        // Your code here
    }
}

Hint

Use a 2D array for DP with dimensions n+1 by totalTime+1. Update dp values by choosing or skipping each activity. Print both results.

Practice

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

easy

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

B. When the problem requires checking all possible solutions

C. When the problem has overlapping subproblems but no optimal substructure

D. When the problem is about sorting large datasets

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.

2. Step 2: Check optimal substructure

   Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

3. Final Answer:

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

4. Quick Check:

   Greedy choice + optimal substructure = Greedy algorithm [OK]

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

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Thinking sorting problems always need DP

2. Which of the following C# code snippets correctly initializes a DP array for a problem with 5 states?

easy

A. int dp = new int[5];

B. int[] dp = new int[5];

C. int[] dp = int[5];

D. int dp[] = new int(5);

Solution

1. Step 1: Check correct array declaration syntax in C#

   Arrays are declared with type[], variable = new type[size]; so int[] dp = new int[5]; is correct.

2. Step 2: Identify errors in other options

   int dp = new int[5]; misses [] for array type, C uses wrong syntax, D uses parentheses instead of brackets.

3. Final Answer:

   int[] dp = new int[5]; -> Option B

4. Quick Check:

   C# array syntax = type[] var = new type[size]; [OK]

Hint: Remember C# arrays use [] and new keyword [OK]

Common Mistakes:

• Missing [] in array type declaration
• Using parentheses instead of brackets for arrays
• Confusing array initialization syntax

3. Consider the following C# code for a problem that can be solved by greedy or DP. What is the output?

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.Length - 1; i >= 0; i--)
{
    count += amount / coins[i];
    amount %= coins[i];
}
Console.WriteLine(count);

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace the greedy coin counting

   Start with coins = {1,3,4}, amount = 6. - i=2 (coin=4): count += 6/4 = 1, amount = 6%4 = 2 - i=1 (coin=3): count += 2/3 = 0, amount = 2%3 = 2 - i=0 (coin=1): count += 2/1 = 2, amount = 2%1 = 0 Total count = 1 + 0 + 2 = 3.

2. Step 2: Confirm output

   The Console.WriteLine prints 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Greedy coin count = 3 [OK]

Hint: Trace loops step-by-step to find output [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Miscomputing division or modulo
• Ignoring order of coins in loop

4. The following code tries to solve the coin change problem using DP but has a bug. What is the error?

int[] coins = {1, 3, 4};
int amount = 6;
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++)
{
    dp[i] = int.MaxValue;
    foreach (int coin in coins)
    {
        if (i - coin >= 0)
        {
            dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
        }
    }
}
Console.WriteLine(dp[amount]);

medium

A. int.MaxValue causes overflow when adding 1

B. dp array is not initialized properly for base case

C. Coins array is not sorted

D. Loop indices are incorrect

Solution

1. Step 1: Understand dp initialization and update

   dp[i] is set to int.MaxValue initially. When dp[i - coin] is int.MaxValue, adding 1 causes overflow.

2. Step 2: Identify overflow problem

   Adding 1 to int.MaxValue wraps around to negative, causing wrong minimum calculation.

3. Final Answer:

   int.MaxValue causes overflow when adding 1 -> Option A

4. Quick Check:

   Adding 1 to int.MaxValue overflows [OK]

Hint: Avoid adding to int.MaxValue directly [OK]

Common Mistakes:

• Ignoring overflow from int.MaxValue + 1
• Assuming coin order matters in DP
• Not initializing dp[0] correctly

5. You want to find the minimum number of coins to make amount 6 using coins {1, 3, 4}. Which approach is better and why?

// Greedy approach
int count = 0;
int amount = 6;
int[] coins = {4, 3, 1};
for (int i = 0; i < coins.Length; i++)
{
    count += amount / coins[i];
    amount %= coins[i];
}
Console.WriteLine(count);

Choose the best answer.

hard

A. Greedy works because coins are sorted descending

B. Neither approach works for this problem

C. Both greedy and DP give same result here

D. Greedy fails; DP is better due to overlapping subproblems

Solution

1. Step 1: Test greedy approach output

   Greedy picks 4 once (6/4=1), remainder 2, picks 3 (2/3=0), remainder 2, picks 1 (2/1=2), total coins = 3.

2. Step 2: Check if greedy is optimal

   DP finds minimum coins: 2 (4 + 2 coins). Greedy gives 3, suboptimal.

3. Step 3: Consider general case

   Greedy can fail for some amounts; DP handles overlapping subproblems and finds true minimum.

4. Final Answer:

   Greedy fails; DP is better due to overlapping subproblems -> Option D

5. Quick Check:

   Overlapping subproblems need DP, greedy may fail [OK]

Hint: Use DP if greedy might miss optimal solution [OK]

Common Mistakes:

• Assuming greedy always works if coins sorted
• Ignoring overlapping subproblems in coin change
• Thinking greedy and DP always match