Unbounded Knapsack (Dynamic Programming)

public class UnboundedKnapsack {
    public static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        // Build up from smaller capacities
        for (int w = 1; w <= capacity; w++) {
            // Try each item type
            for (int i = 0; i < n; i++) {
                // If item fits, try adding it
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
                }
            }
        }
        return dp[capacity];
    }
    // Alternative: 2D DP for clarity
    public static int unboundedKnapsack2D(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 = 1; w <= capacity; w++) {
                // Option 1: Don't include this item type
                dp[i][w] = dp[i - 1][w];
                // Option 2: Include this item (can use again!)
                if (weights[i - 1] <= w) {
                    // Note: dp[i][...] not dp[i-1][...] - can reuse!
                    dp[i][w] = Math.max(dp[i][w],
                        values[i - 1] + dp[i][w - weights[i - 1]]);
                }
            }
        }
        return dp[n][capacity];
    }
    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {10, 40, 50, 70};
        int capacity = 8;
        System.out.println("Max value (1D): " + unboundedKnapsack(weights, values, capacity));
        System.out.println("Max value (2D): " + unboundedKnapsack2D(weights, values, capacity));
        // Output: 110 (take item 3 twice: 50+50+10)
    }
}

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        // dp[i] = minimum coins needed to make amount i
        int[] dp = new int[amount + 1];
        // Initialize with "impossible" value
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;  // Base case: 0 coins for amount 0
        // For each amount
        for (int a = 1; a <= amount; a++) {
            // Try each coin
            for (int coin : coins) {
                if (coin <= a && dp[a - coin] != Integer.MAX_VALUE) {
                    dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    // With backtracking to show which coins
    public static void printCoinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int[] parent = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            parent[i] = -1;
        }
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a && dp[a - coin] != Integer.MAX_VALUE) {
                    if (1 + dp[a - coin] < dp[a]) {
                        dp[a] = 1 + dp[a - coin];
                        parent[a] = coin;
                    }
                }
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) {
            System.out.println("Cannot make amount " + amount);
            return;
        }
        System.out.print("Coins used: ");
        int curr = amount;
        while (curr > 0) {
            System.out.print(parent[curr] + " ");
            curr -= parent[curr];
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("Minimum coins: " + coinChange(coins, amount));
        printCoinChange(coins, amount);
        // Output: 3 coins (5 + 5 + 1)
    }
}

public class CoinChangeWays {
    public static int change(int amount, int[] coins) {
        // dp[a] = number of ways to make amount a
        int[] dp = new int[amount + 1];
        dp[0] = 1;  // One way to make 0: use no coins
        // Process each coin type
        for (int coin : coins) {
            // Update all amounts that can use this coin
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }
    // Important: Process coins in outer loop to avoid duplicates!
    // If we process amounts in outer loop, [1,2] and [2,1] counted separately
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println("Ways to make " + amount + ": " + change(amount, coins));
        // Output: 4 ways
        // [5], [2,2,1], [2,1,1,1], [1,1,1,1,1]
        amount = 3;
        coins = new int[]{2};
        System.out.println("Ways to make " + amount + ": " + change(amount, coins));
        // Output: 0 (cannot make 3 with only 2s)
    }
}