/*
Ques.2: Given n values of coin denominations denoted as d = {d1, d2, d3, ..., dn} 
and an amount A that needs to be covered by selecting the minimum number of coins, 
considering the coin denominations given in set d. In order to cover the amount, any number of coins can 
be selected for the same denomination value. Implement an efficient algorithm to cover the amount 
A by selecting the minimum number of coins.
Note: Show the output by taking any test case on your own.
*/

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

// Function to find minimum number of coins
int minCoins(vector<int>& denominations, int amount) {
    int n = denominations.size();
    
    // Create DP table
    vector<int> dp(amount + 1, INT_MAX);
    vector<int> lastCoin(amount + 1, -1); // To track which coin was used
    
    // Base case
    dp[0] = 0;
    
    // Fill DP table
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < n; j++) {
            if (denominations[j] <= i) {
                int sub_res = dp[i - denominations[j]];
                if (sub_res != INT_MAX && sub_res + 1 < dp[i]) {
                    dp[i] = sub_res + 1;
                    lastCoin[i] = denominations[j];
                }
            }
        }
    }
    
    // Display the coins used
    if (dp[amount] != INT_MAX) {
        cout << "\nCoins used: ";
        int remaining = amount;
        while (remaining > 0) {
            cout << lastCoin[remaining] << " ";
            remaining -= lastCoin[remaining];
        }
        cout << endl;
    }
    
    return dp[amount];
}

int main() {
    // Test Case 1
    cout << "=== COIN CHANGE PROBLEM ===\n";
    vector<int> denominations1 = {1, 2, 5, 10, 20, 50};
    int amount1 = 93;
    
    cout << "Test Case 1:\n";
    cout << "Coin Denominations: ";
    for (int coin : denominations1) {
        cout << coin << " ";
    }
    cout << "\nAmount to cover: " << amount1 << endl;
    
    int result1 = minCoins(denominations1, amount1);
    if (result1 != INT_MAX) {
        cout << "Minimum number of coins needed: " << result1 << endl;
    } else {
        cout << "Amount cannot be formed with given denominations.\n";
    }
    
    // Test Case 2
    cout << "\n---\nTest Case 2:\n";
    vector<int> denominations2 = {1, 3, 4};
    int amount2 = 6;
    
    cout << "Coin Denominations: ";
    for (int coin : denominations2) {
        cout << coin << " ";
    }
    cout << "\nAmount to cover: " << amount2 << endl;
    
    int result2 = minCoins(denominations2, amount2);
    if (result2 != INT_MAX) {
        cout << "Minimum number of coins needed: " << result2 << endl;
    } else {
        cout << "Amount cannot be formed with given denominations.\n";
    }
    
    // Test Case 3 (to demonstrate greedy fails)
    cout << "\n---\nTest Case 3 (Greedy would fail):\n";
    vector<int> denominations3 = {1, 3, 4};
    int amount3 = 6;
    
    cout << "Coin Denominations: ";
    for (int coin : denominations3) {
        cout << coin << " ";
    }
    cout << "\nAmount to cover: " << amount3 << endl;
    cout << "Note: Greedy would choose 4+1+1 (3 coins), but optimal is 3+3 (2 coins)\n";
    
    int result3 = minCoins(denominations3, amount3);
    if (result3 != INT_MAX) {
        cout << "Minimum number of coins needed (Dynamic Programming): " << result3 << endl;
    }
    
    return 0;
}