Why Greedy Works and When It Fails in DSA C - See It Work

Why Greedy Works and When It Fails

📖 Scenario: Imagine you are organizing a small event and need to select tasks to complete within a limited time. You want to pick tasks that give you the most value quickly. This project will help you understand how a greedy approach can work well in some cases but fail in others.

🎯 Goal: You will create a simple program in C that selects tasks based on their value and time using a greedy method. You will see when this approach gives the best result and when it does not.

📋 What You'll Learn

Create an array of tasks with fixed values and durations

Set a total available time limit

Implement a greedy selection of tasks based on value per time

Print the selected tasks and total value

💡 Why This Matters

🌍 Real World

Greedy algorithms are used in scheduling, resource allocation, and decision-making where quick, good-enough solutions are needed.

💼 Career

Understanding greedy algorithms helps in software development roles involving optimization, such as operations research, game development, and system design.

1

Create the tasks array

Create a struct called Task with int value and int duration. Then create an array called tasks with these exact entries: {value: 10, duration: 2}, {value: 5, duration: 1}, {value: 15, duration: 3}, {value: 7, duration: 2}, {value: 6, duration: 1}.

DSA C

// Define struct Task and create tasks array with given values
// Your code here

Hint

Use typedef struct to define Task. Then create tasks array with the exact values.

2

Set the total available time

Add an integer variable called total_time and set it to 5 to represent the total time available for tasks.

DSA C

#include 

typedef struct {
    int value;
    int duration;
} Task;

Task tasks[] = {
    {10, 2},
    {5, 1},
    {15, 3},
    {7, 2},
    {6, 1}
};

int main() {
    int total_time = 5;
    // Your code here
    return 0;
}

Hint

Declare int total_time and assign it the value 5.

3

Select tasks greedily by value per duration

Implement a greedy selection by creating a loop over tasks using for (int i = 0; i < 5; i++). Calculate value per duration as a float and select tasks while total duration does not exceed total_time. Keep track of selected tasks in an integer array selected initialized to 0, and update total used time and total value.

DSA C

#include 

typedef struct {
    int value;
    int duration;
} Task;

Task tasks[] = {
    {10, 2},
    {5, 1},
    {15, 3},
    {7, 2},
    {6, 1}
};

int main() {
    int total_time = 5;
    int selected[5] = {0};
    int used_time = 0;
    int total_value = 0;

    // Your code here

    return 0;
}

Hint

Loop over tasks with for (int i = 0; i < 5; i++). Calculate ratio as float. Select tasks if total duration fits.

4

Print selected tasks and total value

Print the indices of selected tasks using for (int i = 0; i < 5; i++) and if (selected[i]). Then print the total value with printf("Total value: %d\n", total_value);.

DSA C

#include 

typedef struct {
    int value;
    int duration;
} Task;

Task tasks[] = {
    {10, 2},
    {5, 1},
    {15, 3},
    {7, 2},
    {6, 1}
};

int main() {
    int total_time = 5;
    int selected[5] = {0};
    int used_time = 0;
    int total_value = 0;

    for (int i = 0; i < 5; i++) {
        float ratio = (float)tasks[i].value / tasks[i].duration;
        if (used_time + tasks[i].duration <= total_time) {
            selected[i] = 1;
            used_time += tasks[i].duration;
            total_value += tasks[i].value;
        }
    }

    // Your code here

    return 0;
}

Hint

Use printf to show selected task indices and total value.