Dynamic and Greedy Programming in Java
6. Coin Change (Minimum Coins) - Dynamic Programming
Given coins of different denominations and a total amount, find the minimum number of coins
needed to make the amount.
import java.util.*;
public class CoinChange {
public static int coinChange(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];
}
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount = 11;
System.out.println("Minimum coins needed: " + coinChange(coins, amount));
}
}
7. 0/1 Knapsack Problem - Dynamic Programming
Given weights and values of items, put items in a knapsack to get the maximum total value without
exceeding capacity.
public class Knapsack01 {
public static int knapsack(int[] weights, int[] values, int W) {
int n = weights.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i - 1][w],
values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
public static void main(String[] args) {
int[] weights = {1, 3, 4, 5};
int[] values = {1, 4, 5, 7};
int capacity = 7;
System.out.println("Maximum value: " + knapsack(weights, values, capacity));
}
}
8. Activity Selection Problem - Greedy
Select the maximum number of activities that don't overlap, sorted by end time.
import java.util.*;
class Activity {
int start, end;
Activity(int start, int end) {
this.start = start;
this.end = end;
}
}
public class ActivitySelection {
public static int maxActivities(Activity[] activities) {
Arrays.sort(activities, Comparator.comparingInt(a -> a.end));
int count = 1;
int lastEnd = activities[0].end;
for (int i = 1; i < activities.length; i++) {
if (activities[i].start >= lastEnd) {
count++;
lastEnd = activities[i].end;
}
}
return count;
}
public static void main(String[] args) {
Activity[] activities = {
new Activity(1, 3),
new Activity(2, 4),
new Activity(3, 5),
new Activity(0, 6),
new Activity(5, 7),
new Activity(8, 9)
};
System.out.println("Maximum number of activities: " +
maxActivities(activities));
}
}
9. Fractional Knapsack - Greedy
Maximize total value in the knapsack by picking fractions of items based on value-to-weight ratio.
import java.util.*;
class Item {
int value, weight;
Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
}
public class FractionalKnapsack {
public static double getMaxValue(Item[] items, int capacity) {
Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight,
(double)a.value / a.weight));
double totalValue = 0.0;
for (Item item : items) {
if (capacity == 0) break;
if (item.weight <= capacity) {
capacity -= item.weight;
totalValue += item.value;
} else {
totalValue += item.value * ((double) capacity / item.weight);
capacity = 0;
}
}
return totalValue;
}
public static void main(String[] args) {
Item[] items = {
new Item(60, 10),
new Item(100, 20),
new Item(120, 30)
};
int capacity = 50;
System.out.println("Maximum value: " + getMaxValue(items, capacity));
}
}
