Greedy Algorithms in C - Activity Selection, Huffman

Greedy Approach

A greedy algorithm makes the locally optimal choice at each step hoping to find the global optimum.

Characteristics

Makes locally optimal choices
Never reconsiders choices
Faster but doesn't always give optimal solution

Activity Selection Problem

Select maximum number of activities that don't overlap.

activity_selection.c

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Activity;

// Compare by finish time
int compare(const void* a, const void* b) {
    return ((Activity*)a)->end - ((Activity*)b)->end;
}

void activitySelection(Activity arr[], int n) {
    // Sort by finish time
    qsort(arr, n, sizeof(Activity), compare);
    
    printf("Selected activities:\n");
    
    // Select first activity
    int i = 0;
    printf("Activity 1: (%d, %d)\n", arr[i].start, arr[i].end);
    
    // Consider remaining activities
    for (int j = 1; j < n; j++) {
        if (arr[j].start >= arr[i].end) {
            printf("Activity %d: (%d, %d)\n", j + 1, arr[j].start, arr[j].end);
            i = j;
        }
    }
}

int main() {
    Activity arr[] = {{1, 3}, {2, 5}, {4, 7}, {1, 8}, {5, 9}, {8, 10}};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    activitySelection(arr, n);
    return 0;
}

Fractional Knapsack

Can take fractions of items to maximize value.

fractional_knapsack.c

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int value;
    int weight;
    double ratio;
} Item;

int compare(const void* a, const void* b) {
    double r1 = ((Item*)a)->ratio;
    double r2 = ((Item*)b)->ratio;
    return (r1 > r2) ? -1 : 1;
}

double fractionalKnapsack(Item items[], int n, int W) {
    // Calculate value/weight ratio
    for (int i = 0; i < n; i++)
        items[i].ratio = (double)items[i].value / items[i].weight;
    
    // Sort by ratio (descending)
    qsort(items, n, sizeof(Item), compare);
    
    double totalValue = 0.0;
    
    for (int i = 0; i < n && W > 0; i++) {
        if (items[i].weight <= W) {
            // Take whole item
            totalValue += items[i].value;
            W -= items[i].weight;
        } else {
            // Take fraction
            totalValue += items[i].ratio * W;
            W = 0;
        }
    }
    
    return totalValue;
}

int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = sizeof(items) / sizeof(items[0]);
    int W = 50;
    
    printf("Maximum value: %.2f\n", fractionalKnapsack(items, n, W));
    return 0;
}

Greedy vs DP

Greedy	Dynamic Programming
Local optimization	Global optimization
Faster	Slower
No backtracking	Considers all possibilities
May not be optimal	Always optimal