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 [Link].*;
public class CoinChange {
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
[Link](dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = [Link](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;
[Link]("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 = [Link];
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] = [Link](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;
[Link]("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 [Link].*;
class Activity {
int start, end;
Activity(int start, int end) {
[Link] = start;
[Link] = end;
}
}
public class ActivitySelection {
public static int maxActivities(Activity[] activities) {
[Link](activities, [Link](a -> [Link]));
int count = 1;
int lastEnd = activities[0].end;
for (int i = 1; i < [Link]; 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)
};
[Link]("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 [Link].*;
class Item {
int value, weight;
Item(int value, int weight) {
[Link] = value;
[Link] = weight;
}
}
public class FractionalKnapsack {
public static double getMaxValue(Item[] items, int capacity) {
[Link](items, (a, b) -> [Link]((double)[Link] / [Link],
(double)[Link] / [Link]));
double totalValue = 0.0;
for (Item item : items) {
if (capacity == 0) break;
if ([Link] <= capacity) {
capacity -= [Link];
totalValue += [Link];
} else {
totalValue += [Link] * ((double) capacity / [Link]);
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;
[Link]("Maximum value: " + getMaxValue(items, capacity));
}
}