Given a set of coin denominations and a total amount, find the minimum number of coins needed to make that amount.

Key Concepts

1. Dynamic Programming: This approach is effective for solving problems where the solution can be composed of solutions to subproblems. Here, we can build up the solution using previously computed results.
2. State Representation: We can use a one-dimensional array dp where dp[i] represents the minimum number of coins needed to make the amount i.

Dynamic Programming Approach

• Step 1: Initialize an array dp of size amount + 1, filled with a value larger than the maximum possible coins (like amount + 1).
• Step 2: Set dp[0] = 0 because no coins are needed to make zero amount.
• Step 3: For each coin denomination, update the dp array based on whether including the coin will result in fewer coins needed for each amount.

C Program for Minimum Coin Change

Here’s a complete C program to solve the Minimum Coin Change problem:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Function to find the minimum number of coins for a given amount
int minCoins(int coins[], int numCoins, int amount) {
    // Create a DP array and initialize it with a high value
    int* dp = (int*)malloc((amount + 1) * sizeof(int));
    for (int i = 0; i <= amount; i++) {
        dp[i] = INT_MAX; // Initialize to infinity
    }
    
    // Base case: No coins are needed to make amount 0
    dp[0] = 0;

    // Compute minimum coins required for all amounts
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < numCoins; j++) {
            if (coins[j] <= i) {
                if (dp[i - coins[j]] != INT_MAX) {
                    dp[i] = (dp[i] < dp[i - coins[j]] + 1) ? dp[i] : (dp[i - coins[j]] + 1);
                }
            }
        }
    }

    // If dp[amount] is still infinity, return -1
    int result = (dp[amount] == INT_MAX) ? -1 : dp[amount];

    // Free the allocated memory
    free(dp);
    
    return result;
}

// Main function
int main() {
    int numCoins, amount;

    // Input the number of coins
    printf("Enter the number of coin denominations: ");
    scanf("%d", &numCoins);

    int* coins = (int*)malloc(numCoins * sizeof(int));

    // Input the coin denominations
    printf("Enter the coin denominations: ");
    for (int i = 0; i < numCoins; i++) {
        scanf("%d", &coins[i]);
    }

    // Input the total amount
    printf("Enter the amount to make change for: ");
    scanf("%d", &amount);

    // Find the minimum number of coins
    int minCoinsRequired = minCoins(coins, numCoins, amount);
    if (minCoinsRequired != -1) {
        printf("Minimum number of coins needed: %d\n", minCoinsRequired);
    } else {
        printf("It is not possible to make the given amount with the provided denominations.\n");
    }

    // Free the allocated memory
    free(coins);

    return 0;
}

Explanation of the Code

1. Dynamic Programming Table:
   • We create a one-dimensional array dp where dp[i] stores the minimum number of coins needed to make the amount i.
2. Filling the DP Array:
   • We initialize the dp array to a large value (INT_MAX) to represent that those amounts cannot be formed initially.
   • For each amount from 1 to amount, we check each coin denomination. If the coin can be used (i.e., its value is less than or equal to the current amount), we update the dp[i] value.
3. Final Result:
   • After populating the dp array, we check dp[amount]. If it is still INT_MAX, it means that the amount cannot be formed with the given coins, and we return -1.
4. Memory Management:
   • The program dynamically allocates memory for the coins and the dp array and frees it at the end to prevent memory leaks.

Input and Output Example

Input

mathematicaCopy codeEnter the number of coin denominations: 3
Enter the coin denominations: 1 3 4
Enter the amount to make change for: 6

Output

typescriptCopy codeMinimum number of coins needed: 2

Explanation of the Output

In this example, the minimum number of coins needed to make the amount 6 is 2, which can be achieved by using two coins of denomination 3.

Conclusion

This C program efficiently solves the Minimum Coin Change problem using dynamic programming. It allows for user input for flexibility and computes the minimum number of coins required to achieve a given amount with specified denominations. You can test various coin sets and amounts to see how the solution adapts. This approach is widely applicable in financial calculations and resource allocation problems.