找零钱问题贪心算法c

贪心算法是一种常用的解决找零钱问题的方法。其核心思想是在每一步中选择最优解，从而得到全局最优解。在找零钱问题中，贪心算法采取的方式是找钱时，总是选取可供找钱的硬币的最大值。比如，需要找钱数为25时，找钱方式为20+5，而不是10+10+5。

下面是一个使用C语言实现的找零钱问题的贪心算法的例子：

/* 
 * m[ ]:存放可供找零的面值，降序排列 
 * k:可供找零的面值种类数 ,即m[ ]的长度 
 * n:需要找零数 
 */ 
#include <stdio.h> 

void getmoney(int m[],int k,int n){ 
    int i; 
    for( i=0;i<k;i++) { 
        while(n>=m[i]) { 
            printf("%d ",m[i]); 
            n=n-m[i]; 
        } 
    } 
    printf("\n"); 
} 

int main(){ 
    int n; 
    scanf("%d",&n); 
    int money[]={20,10,5,1}; 
    int k; 
    k=sizeof(money)/sizeof(int); 
    getmoney(money,k,n); 
} 

相关问题

找零钱问题贪心算法c语言

找零钱问题是指在给定一定面额的硬币和需要找零的金额的情况下，如何使用最少的硬币找找零钱问题是指在给定一定面额的硬币和需要找零的金额的情况下，如何使用最少的硬币找零。贪心算法是一种常用的解决此类问题的方法，它的思路是每次选择当前可用的最大面额的硬币进行找零，直到找完为止。在C语言中，可以使用循环嵌套的方式来实现贪心算法解决找零钱问题。具体实现可以参考引用中的代码。同时，引用和引用中也提供了关于贪心算法的思路和实现方式的介绍。

找零钱问题贪心算法c语言代码

以下是C语言实现找零钱问题的贪心算法代码，该算法从最大面额硬币开始尝试找零，以减少硬币数量：

#include <stdio.h>

void findMinCoins(int coins[], int n, int amount)
{
    int coinCount[n];
    for (int i = 0; i < n; i++) {
        coinCount[i] = 0;
    }
    for (int i = n - 1; i >= ; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            coinCount[i        }
    }
    printf("找零的硬币数量为：\n");
    for (int i = n - 1; i >= 0; i--) {
        if (coinCount[i] != 0) {
            printf("%d 个 %d 元硬币\n", coinCount[i], coins[i]);
        }
    }
}

int main()
{
    int coins[] = { 1, 2, 5, 10, 20, 50, 100 };
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 78;
    findMinCoins(coins, n, amount);
    return 0;
}