GREEDY ALGORITHMS
Greedy algorithms are a class of algorithms that make locally optimal choices at each step in the hope of finding a global optimum solution. In other words, the algorithm selects the best option at each step, without looking ahead, and hopes that this will lead to the best possible solution. Greedy algorithms work well for certain types of problems, but may not always produce the best possible solution.
A classic example of a problem that can be solved using a greedy algorithm is the coin change problem. The problem is to find the minimum number of coins required to make change for a given amount of money. For example, suppose you want to make change for 67 cents. You have an unlimited supply of coins in denominations of 1, 5, 10, 25 cents. What is the minimum number of coins you need to make the change?
A greedy algorithm for this problem would start by selecting the largest coin denomination that can be used to make the change. In this case, the largest coin denomination is 25 cents. You can use two 25 cents coins to make 50 cents of the change, and then two 10 cents coins and one 1 cent coin to make the remaining 17 cents of the change, for a total of 5 coins. This is the optimal solution, and the greedy algorithm correctly found it.
In general, greedy algorithms work best when the problem has the following properties:
- Greedy choice property: A global optimum can be obtained by making a locally optimal choice at each step.
- Optimal substructure: The optimal solution to a problem can be obtained by combining the optimal solutions to its subproblems.
However, not all problems have these properties, and greedy algorithms may not always produce the optimal solution. It's important to carefully analyze the problem and determine whether a greedy algorithm is appropriate before using it.
Here's an example implementation of the "Fractional Knapsack" problem, which is a classic problem that can be solved using a greedy algorithm:
import java.util.*;
class Item implements Comparable<Item> {
private int weight;
private int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
public double getValuePerUnitWeight() {
return (double) value / weight;
}
public int compareTo(Item other) {
double ratio = this.getValuePerUnitWeight() -
other.getValuePerUnitWeight();
return (ratio > 0) ? -1 : (ratio < 0) ? 1 :
0;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
}
public class FractionalKnapsack {
public static double getMaxValue(int[] weights, int[] values, int
capacity) {
Item[] items = new Item[weights.length];
for (int i = 0; i < weights.length; i++) {
items[i] = new Item(weights[i],
values[i]);
}
Arrays.sort(items);
double maxValue = 0;
for (Item item : items) {
int weight = item.getWeight();
int value = item.getValue();
if (capacity >= weight) {
maxValue += value;
capacity -= weight;
} else {
double fraction = ((double)
capacity) / weight;
maxValue += value *
fraction;
break;
}
}
return maxValue;
}
public static void main(String[] args) {
int[] weights = {10, 20, 30};
int[] values = {60, 100, 120};
int capacity = 50;
double maxValue = getMaxValue(weights, values,
capacity);
System.out.println("Max value for capacity " +
capacity + ": " + maxValue);
}
}
In this implementation, getMaxValue() takes in an array of weights, an array of values, and a capacity. It creates an array of Item objects with each item containing its weight and value. It then sorts these items by their value-to-weight ratio using Arrays.sort(), and iterates through each item. If the capacity is greater than or equal to the item's weight, the item is added to the knapsack and its weight is subtracted from the capacity. If the capacity is less than the item's weight, a fraction of the item is added to the knapsack, proportional to the capacity remaining.
This is a greedy algorithm because it selects the items with the highest value-to-weight ratio at each step, without considering the impact of that choice on future selections. This algorithm works correctly for the fractional knapsack problem, but may not work for all problems.