WikiGalaxy
Greedy Algorithm vs Dynamic Programming
Introduction:
Greedy algorithms and dynamic programming are two fundamental algorithm design paradigms used to solve optimization problems. Understanding the differences and when to apply each technique is crucial for efficient problem-solving.
Example 1: Coin Change Problem
Problem Description:
Given a set of coin denominations and a total amount, determine the minimum number of coins needed to make the amount.
Greedy Approach:
The greedy algorithm selects the largest denomination coin first and continues selecting the largest possible coins until the amount is met.
Dynamic Programming Approach:
Dynamic programming solves this problem by building a table that stores the minimum coins needed for each amount up to the target.
public class CoinChange {
public int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
Console Output:
3
Example 2: Knapsack Problem
Problem Description:
Given weights and values of items, determine the maximum value that can be obtained with a given weight capacity.
Greedy Approach:
The greedy algorithm sorts items based on value/weight ratio and picks items until the capacity is full.
Dynamic Programming Approach:
Dynamic programming builds a table where each entry represents the maximum value obtainable with a given weight capacity.
public class Knapsack {
public int knapsackDP(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
}
Console Output:
220
Example 3: Activity Selection
Problem Description:
Given a set of activities with start and finish times, select the maximum number of non-overlapping activities.
Greedy Approach:
The greedy algorithm selects activities based on the earliest finish time, ensuring maximum activity selection.
Dynamic Programming Approach:
Although the greedy approach is optimal here, dynamic programming can be used to explore all subsets for educational purposes.
public class ActivitySelection {
public List selectActivities(int[] start, int[] finish) {
List selected = new ArrayList<>();
int n = start.length;
int lastFinish = 0;
for (int i = 0; i < n; i++) {
if (start[i] >= lastFinish) {
selected.add(i);
lastFinish = finish[i];
}
}
return selected;
}
}
Console Output:
[0, 2, 4]
Example 4: Fractional Knapsack Problem
Problem Description:
Given weights and values of items, determine the maximum value obtainable with a given weight capacity, allowing fractions of items.
Greedy Approach:
The greedy algorithm sorts items based on value/weight ratio and fills the knapsack with the highest ratio items first.
public class FractionalKnapsack {
public double fractionalKnapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
ItemValue[] items = new ItemValue[n];
for (int i = 0; i < n; i++) {
items[i] = new ItemValue(weights[i], values[i]);
}
Arrays.sort(items, Comparator.comparingDouble(ItemValue::getRatio).reversed());
double totalValue = 0;
for (ItemValue item : items) {
int curWeight = (int) item.weight;
int curValue = (int) item.value;
if (capacity - curWeight >= 0) {
capacity -= curWeight;
totalValue += curValue;
} else {
double fraction = ((double) capacity / curWeight);
totalValue += (curValue * fraction);
break;
}
}
return totalValue;
}
class ItemValue {
Double weight, value;
Double getRatio() { return value / weight; }
ItemValue(double weight, double value) { this.weight = weight; this.value = value; }
}
}
Console Output:
240.0
Example 5: Longest Common Subsequence
Problem Description:
Given two sequences, find the length of the longest subsequence present in both of them.
Dynamic Programming Approach:
A table is constructed to store lengths of longest common subsequences of substrings. The table is filled in a bottom-up fashion.
public class LongestCommonSubsequence {
public int lcs(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
Console Output:
4
