Introduction to Greedy Algorithms

Greedy algorithms are a straightforward approach to solving optimization problems. They make the "locally optimal" choice at each step with the hope of finding a global optimum. While not always guaranteed to find the absolute best solution, they are often efficient and provide a good approximation, especially in problems where the optimal substructure property and greedy choice property hold.

Fractional Knapsack Problem

The fractional knapsack problem involves filling a knapsack with a limited weight capacity with items that have a value and a weight. Unlike the 0/1 knapsack problem, we are allowed to take fractions of items.

Problem Statement

Given a knapsack with capacity W and a list of items, each with a weight wi and a value vi, determine the maximum value of items that can be placed in the knapsack. You can take fractions of items.

Greedy Approach

The greedy strategy is to select items with the highest value-to-weight ratio (vi/wi) first. We sort the items based on this ratio in descending order. We then iterate through the sorted items, adding as much of each item as possible to the knapsack until it's full.

Java Solution

 import java.util.Arrays;
import java.util.Comparator;

class Item {
    int index;
    double value;
    double weight;
    double ratio; //value/weight

    public Item(int index, double value, double weight) {
        this.index = index;
        this.value = value;
        this.weight = weight;
        this.ratio = value / weight;
    }
}

public class FractionalKnapsack {

    public static double fractionalKnapsack(int capacity, Item[] items) {
        Arrays.sort(items, Comparator.comparingDouble(i -> i.ratio).reversed());

        double totalValue = 0;
        for (Item item : items) {
            if (capacity == 0) {
                break;
            }

            double amountToTake = Math.min(item.weight, capacity);
            totalValue += amountToTake * item.ratio;
            capacity -= amountToTake;
        }

        return totalValue;
    }

    public static void main(String[] args) {
        int capacity = 50;
        Item[] items = {
                new Item(0, 60, 10),
                new Item(1, 100, 20),
                new Item(2, 120, 30)
        };

        double maxValue = fractionalKnapsack(capacity, items);
        System.out.println("Maximum value: " + maxValue); // Output: 240.0
    }
} 

Explanation

1. We create an Item class to store the value, weight, and value-to-weight ratio of each item.
2. We sort the items array in descending order based on the value-to-weight ratio.
3. We iterate through the sorted items, taking as much of each item as possible until the knapsack is full.
4. The Math.min(item.weight, capacity) determines how much of the current item can be taken without exceeding the knapsack capacity.

Activity Selection Problem

The activity selection problem involves selecting a maximum-size set of mutually compatible activities from a set of activities with given start and finish times.

Problem Statement

Given a set of activities, each with a start time si and a finish time fi, select a maximum-size subset of mutually compatible activities. Two activities are compatible if they do not overlap.

Greedy Approach

The greedy strategy is to select activities that finish earliest. We sort the activities by their finish times in ascending order. We then select the first activity and iterate through the remaining activities, selecting an activity if it is compatible with the previously selected activities (i.e., its start time is greater than or equal to the finish time of the last selected activity).

Java Solution

 import java.util.Arrays;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.List;

class Activity {
    int start;
    int finish;

    public Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {

    public static List<Activity> selectActivities(Activity[] activities) {
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        List<Activity> selectedActivities = new ArrayList<>();
        selectedActivities.add(activities[0]); // Select the first activity (earliest finish time)

        int lastFinishTime = activities[0].finish;

        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastFinishTime) {
                selectedActivities.add(activities[i]);
                lastFinishTime = activities[i].finish;
            }
        }

        return selectedActivities;
    }

    public static void main(String[] args) {
        Activity[] activities = {
                new Activity(1, 2),
                new Activity(3, 4),
                new Activity(0, 6),
                new Activity(5, 7),
                new Activity(8, 9),
                new Activity(5, 9)
        };

        List<Activity> selected = selectActivities(activities);

        System.out.println("Selected activities:");
        for (Activity activity : selected) {
            System.out.println("(" + activity.start + ", " + activity.finish + ")");
        }
        //Expected Output: (1, 2), (3, 4), (5, 7), (8, 9) or similar, depending on sort stability if start times are the same.
    }
} 

Explanation

1. We create an Activity class to store the start and finish times of each activity.
2. We sort the activities array in ascending order based on the finish times.
3. We select the first activity (the one that finishes earliest).
4. We iterate through the remaining activities, selecting an activity if its start time is greater than or equal to the finish time of the last selected activity.

Conclusion

Greedy algorithms provide a powerful and efficient way to solve optimization problems. Understanding the principles behind them and being able to identify problems where they are applicable is a valuable skill in competitive programming. Remember to always consider whether the greedy choice property and optimal substructure hold before applying a greedy algorithm, and be prepared to justify its correctness.