algorithms3GreedyAlgorithms

1package pkg4algorithms;2 3/*4 * algorithms3GreedyAlgorithms.java5 * ---------------------6 * Greedy = make the locally optimal choice at each step, hoping for a global7 * optimum. Works when the problem has the "greedy-choice property".8 *9 * Examples: activity selection, fractional knapsack, coin change (canonical coins).10 */11import java.util.*;12 13public class algorithms3GreedyAlgorithms {14 15    // Activity selection: max non-overlapping activities. Greedy: pick earliest finish.16    static List<int[]> activitySelection(int[][] activities) {17        Arrays.sort(activities, Comparator.comparingInt(a -> a[1]));   // by finish time18        List<int[]> chosen = new ArrayList<>();19        int lastEnd = Integer.MIN_VALUE;20        for (int[] act : activities) {21            if (act[0] >= lastEnd) { chosen.add(act); lastEnd = act[1]; }22        }23        return chosen;24    }25 26    // Fractional knapsack: take highest value/weight ratio first (fractions allowed).27    static double fractionalKnapsack(int capacity, int[][] items) {28        Arrays.sort(items, (a, b) -> Double.compare((double) b[0] / b[1], (double) a[0] / a[1]));29        double total = 0;30        for (int[] it : items) {31            int value = it[0], weight = it[1];32            if (capacity >= weight) { total += value; capacity -= weight; }33            else { total += value * ((double) capacity / weight); break; }34        }35        return total;36    }37 38    // Coin change (greedy works for canonical systems like {1,5,10,25}).39    static List<Integer> coinChangeGreedy(int amount, int[] coins) {40        Arrays.sort(coins);41        List<Integer> used = new ArrayList<>();42        for (int i = coins.length - 1; i >= 0; i--) {43            while (amount >= coins[i]) { used.add(coins[i]); amount -= coins[i]; }44        }45        return used;46    }47 48    public static void main(String[] args) {49        int[][] acts = {{1, 3}, {2, 5}, {4, 7}, {1, 8}, {5, 9}, {8, 10}};50        System.out.println("activities chosen:");51        activitySelection(acts).forEach(a -> System.out.println("  [" + a[0] + "," + a[1] + "]"));52 53        int[][] items = {{60, 10}, {100, 20}, {120, 30}};   // {value, weight}54        System.out.println("fractional knapsack (cap 50) max value: " + fractionalKnapsack(50, items));55 56        System.out.println("coin change 87 with {1,5,10,25}: " + coinChangeGreedy(87, new int[]{1, 5, 10, 25}));57    }58}