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 managing a small delivery service. You have a list of packages, each with a weight and a value. You want to maximize the total value of packages you can carry without exceeding your truck's weight limit.This is a classic problem where you can try two approaches: a simple greedy method or a more careful dynamic programming method.

🎯 Goal: Build a program that first tries a greedy approach to select packages by value-to-weight ratio, then uses dynamic programming to find the best combination. Learn how to decide which method works better.

📋 What You'll Learn

Create an array of packages with exact weights and values

Create a variable for the truck's weight limit

Implement a greedy selection based on value-to-weight ratio

Implement a dynamic programming solution for the knapsack problem

Print the total value selected by both methods

💡 Why This Matters

🌍 Real World

Delivery services, resource allocation, and budgeting problems often require choosing the best combination of items under constraints.

💼 Career

Understanding greedy and dynamic programming helps in software engineering roles involving optimization, algorithm design, and problem solving.

1

Create the packages array

Create an array called packages of 4 elements where each element is a struct with weight and value. Use these exact values: package 0: weight 2, value 3; package 1: weight 3, value 4; package 2: weight 4, value 5; package 3: weight 5, value 8.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    // Create the packages array with 4 elements
    // Your code here

Hint

Define packages as an array of 4 Package structs with the given weights and values.

2

Set the truck's weight limit

Create an integer variable called weight_limit and set it to 8.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    struct Package packages[4] = {
        {2, 3},
        {3, 4},
        {4, 5},
        {5, 8}
    };
    // Set the weight limit to 8
    // Your code here

Hint

Just create an integer weight_limit and assign it the value 8.

3

Implement the greedy selection

Write code to select packages greedily by value-to-weight ratio. Create an array selected of 4 integers initialized to 0. Then, select packages in order of highest value/weight ratio without exceeding weight_limit. Use variables total_weight and total_value_greedy to track weight and value. Use a simple sorting approach by swapping packages based on ratio.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    struct Package packages[4] = {
        {2, 3},
        {3, 4},
        {4, 5},
        {5, 8}
    };
    int weight_limit = 8;
    // Implement greedy selection by value-to-weight ratio
    // Your code here

Hint

Sort packages by value/weight ratio, then pick packages while total weight is within limit.

4

Implement dynamic programming and print results

Implement a dynamic programming solution to find the maximum value for the weight limit. Create a 2D array dp of size 5 by 9 (for 4 packages + 1 and weight limit + 1). Fill dp using the knapsack logic. Then print the total value from greedy as Greedy total value: X and from DP as DP total value: Y where X and Y are the computed values.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    struct Package packages[4] = {
        {2, 3},
        {3, 4},
        {4, 5},
        {5, 8}
    };
    int weight_limit = 8;

    int selected[4] = {0, 0, 0, 0};
    int total_weight = 0;
    int total_value_greedy = 0;

    // Simple bubble sort by value/weight ratio descending
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3 - i; j++) {
            double ratio_j = (double)packages[j].value / packages[j].weight;
            double ratio_j1 = (double)packages[j+1].value / packages[j+1].weight;
            if (ratio_j < ratio_j1) {
                struct Package temp = packages[j];
                packages[j] = packages[j+1];
                packages[j+1] = temp;
            }
        }
    }

    for (int i = 0; i < 4; i++) {
        if (total_weight + packages[i].weight <= weight_limit) {
            selected[i] = 1;
            total_weight += packages[i].weight;
            total_value_greedy += packages[i].value;
        }
    }

    // Implement DP knapsack and print results
    // Your code here

Hint

Use the classic knapsack DP approach. Then print both totals exactly as shown.

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 combinations

C. When the problem has overlapping subproblems but no greedy choice

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: Compare with dynamic programming conditions

   Dynamic programming is used when subproblems overlap and greedy choice property does not hold.

3. Final Answer:

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

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 with greedy choice
• Using greedy when problem needs full exploration
• Assuming sorting problems always need greedy

2. Which of the following is the correct syntax to declare a memoization array for dynamic programming in C?

easy

A. int memo[1000] = {0};

B. int memo[] = 0;

C. int memo(1000) = {0};

D. int memo = new int[1000];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with fixed size and optional initialization using braces.

2. Step 2: Check each option

   int memo[1000] = {0}; correctly declares an int array of size 1000 initialized to zero. Others are invalid C syntax.

3. Final Answer:

   int memo[1000] = {0}; -> Option A

4. Quick Check:

   C arrays use [] with size [OK]

Hint: Use int arr[size] = {0} for zero-initialized arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Trying to assign 0 directly to array
• Using new keyword in C (it's C++ syntax)

3. What is the output of the following C code snippet that uses a greedy approach to select coins?

int coins[] = {1, 5, 10, 25};
int amount = 30;
int count = 0;
for (int i = 3; i >= 0; i--) {
    while (amount >= coins[i]) {
        amount -= coins[i];
        count++;
    }
}
printf("%d\n", count);

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace the greedy coin selection

   Start with coin 25: amount=30, 30>=25, subtract 25, amount=5, count=1.

2. Step 2: Continue with smaller coins

   Next coin 10: amount=5<10, skip. Next coin 5: amount=5>=5, subtract 5, amount=0, count=2.

3. Step 3: No more coins needed

   Loop ends, total coins used = 2.

4. Final Answer:

   2 -> Option C

5. Quick Check:

   25 + 5 = 30 using 2 coins [OK]

Hint: Subtract largest coin repeatedly until amount zero [OK]

Common Mistakes:

• Counting coins incorrectly in loops
• Not updating amount after subtraction
• Confusing coin order in loop

4. The following code attempts to solve the Fibonacci sequence using a greedy approach. What is the error?

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

medium

A. Loop should start from i = 1 instead of 2

B. No error, code correctly computes Fibonacci

C. Variable c is not initialized properly

D. Greedy approach is incorrect for Fibonacci calculation

Solution

1. Step 1: Understand Fibonacci calculation

   Fibonacci requires summing previous two numbers, which is a classic dynamic programming problem.

2. Step 2: Identify greedy approach misuse

   The code uses iteration correctly but calling it greedy is wrong because Fibonacci does not have greedy choice property.

3. Final Answer:

   Greedy approach is incorrect for Fibonacci calculation -> Option D

4. Quick Check:

   Fibonacci needs DP, not greedy [OK]

Hint: Fibonacci needs DP, greedy won't work [OK]

Common Mistakes:

• Thinking iterative is greedy
• Ignoring problem properties
• Confusing initialization with error

5. You want to find the minimum number of coins to make change for a given amount using coins of denominations {1, 3, 4}. Which approach is best and why?

hard

A. Greedy, because always picking the largest coin works here

B. Dynamic Programming, because greedy fails for some amounts

C. Brute force, because both greedy and DP are too complex

D. Sorting coins and picking smallest first

Solution

1. Step 1: Test greedy approach on example

   For amount 6, greedy picks 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins.

2. Step 2: Recognize overlapping subproblems

   Dynamic programming stores solutions for smaller amounts to build up answer correctly.

3. Step 3: Conclude best approach

   Greedy fails due to lack of greedy choice property; DP handles all cases optimally.

4. Final Answer:

   Dynamic Programming, because greedy fails for some amounts -> Option B

5. Quick Check:

   Greedy fails, DP works [OK]

Hint: Test greedy on small cases; if fails, use DP [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring counterexamples
• Choosing brute force unnecessarily