硬币找零算法C

Question

我在想出解决以下问题的有效算法时遇到了一些麻烦。

给定 100、50、25 和 10 美分的可用硬币数量，我需要找到如何将这些硬币的组合放入给定值 x。（它不一定是最佳的，可用硬币的任何组合都可以）。

到目前为止，我得到了这段代码，它只适用于某些情况。

struct coins{
    int valor;
    int quant;
};

int change = 0;
int changecoins[4] = {0};
struct coins available_coins[4] = { 0 };

moedas_disp[3].value = 10; //10 cents coins
moedas_disp[2].value = 25; //25 cents coins
moedas_disp[1].value = 50;  //50 cents coins
moedas_disp[0].value = 100; //100 cents coins

//quantity values just for test purposes
moedas_disp[3].quant = 10; //10 cents coins
moedas_disp[2].quant = 15; //25 cents coins
moedas_disp[1].quant = 8;  //50 cents coins
moedas_disp[0].quant = 12; //100 cents coins


for(int i=0; i<4; i++){
    while((change/available_coins[i].value>0)&&(available_coins[i].quant>0)){
        change -= available_coins[i].value;
        available_coins[i].quant--;
        changecoins[i]++;
    }
}
if(change>0){
    printf("It was not possible to change the value");
}
else{
    printf("Change:\n");
    printf("\t%d 100 cent coin(s).\n", changecoins[0]);
    printf("\t%d 50 cent coin(s).\n", changecoins[1]);
    printf("\t%d 25 cent coin(s).\n", changecoins[2]);
    printf("\t%d 10 cent coin(s).\n", changecoins[3]);
}

但是对于像 30 这样的数量，这将不起作用。该程序将适合 1 枚 25 美分的硬币，但还剩下 5 美分，这将无法计算。 40、65 等也会出现这种情况。

提前致谢！

Answer 1

您可以按照以下步骤使用递归算法：

拿出 1 100c 硬币，尝试将剩余金额分解为 50、25、10s
如果这不起作用，取 2 100c 硬币并尝试将剩余金额分解为 50、25、10 秒
等等

如果您尝试了 100c 硬币数量（包括 0！）的所有可能性，那么您将涵盖所有可能的解决方案。

我写了一些演示代码。如果这是家庭作业，那么请不要 copy-paste 我的代码，但一旦你理解了所涉及的想法，就可以编写你自己的代码 ...

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

bool coin_find(unsigned int total, unsigned int *denom)
{
    if ( total == 0 )
        return true;    // Success - reduced total remaining to 0

    if ( *denom == 0 )
        return false;   // Failure - tried all coins in the list with no solution yet

    // Try 0 of the largest coin, then 1, etc.
    for (unsigned int d = 0; ; ++d)
    {
        if ( d * *denom > total )
            return false;

        if ( coin_find(total - d * *denom, denom + 1) )
        {
            if ( d ) 
                printf("%ux%uc ", d, *denom);
            return true;
        }
    }
}

int main(int argc, char **argv)
{
    if ( argc < 2 )
        return EXIT_FAILURE;

    unsigned int denoms[] = { 100, 50, 25, 10, 0 };

    long t = strtol(argv[1], NULL, 10);
    if ( t < 0 || t >= LONG_MAX )
        return EXIT_FAILURE;

    if ( !coin_find(t, denoms) )
        printf("No solution found");

    printf("\n");
}

reader 的练习：

向后循环而不是向前循环，以便我们默认找到更整洁的解决方案。
只输出硬币数量最少的细分。
输出所有可能的故障。

奖金练习：

重写为根本不使用递归；而是使用一个包含到目前为止的解决方案的数组，并在到达终点时使用 backtrack。这样实际上练习 3 会更容易。

Answer 2

下面的解决方案使用了动态规划，只要M（x对你来说）的值很小就可以使用它。如果 prev[j] 不同于 -1 那么这意味着 j 可以用给定的硬币制作。 coin[j]存储用来制作j的硬币的价值，prev[j]是没有使用coin[j]的价值。因此，(j - prev[j]) / coin[j] 为我们提供了面额 coin[j] 的硬币数量，用于制作重量 j.

#include <stdio.h>

const int
    COINS = 4;

int M = 1100; 
int prev[10000];
int coin[10000];
// Available denominations.
int value[COINS] = { 10, 25, 50, 100 };
// Available quantities.
int quant[COINS] = { 10, 15, 8, 12 };
// Number of selected coins per denomination.
int answer[COINS] = { 0, 0, 0, 0 };

int main() {
    // base case    
    prev[0] = 0;
    for (int i = 1; i < 10000; i++)
        prev[i] = -1;

    // dynamic programming
    for (int i = 0; i < COINS; i++)
        for (int j = M; j >= 0; j--)
            if (prev[j] != -1) {
                int k = 1;
                while (k <= quant[i] && j + k * value[i] <= M) {
                    if (prev[j + k * value[i]] == -1) {
                        prev[j + k * value[i]] = j;
                        coin[j + k * value[i]] = value[i];
                    }
                    k++;
                }
            }

    // build the answer
    if (prev[M] != -1) {
        int current = M;
        while (current > 0) {
            int k = 0;
            while (k < COINS && coin[current] != value[k])
                k++;
            answer[k] += (current - prev[current]) / coin[current];
            current = prev[current];
        }
        printf("Change\n");
        for (int i = 0; i < COINS; i++)
            printf("\t%d %d cent coin(s).\n", answer[i], value[i]);
    } else {
        printf("It was not possible to change the value");
    }

    return 0;
}

Answer 3

因为25%10不等于0，你需要考虑一下。试试这个算法：

#include <stdio.h>

struct coins{
    int value;
    int quant;
};

int main()
{
    int change = 30;
    int changecoins[4] = {0};
    struct coins available_coins[4] = { 0 };
    int temp;

    available_coins[3].value = 10; //10 cents coins
    available_coins[2].value = 25; //25 cents coins
    available_coins[1].value = 50;  //50 cents coins
    available_coins[0].value = 100; //100 cents coins

    //quantity values just for test purposes
    available_coins[3].quant = 10; //10 cents coins
    available_coins[2].quant = 15; //25 cents coins
    available_coins[1].quant = 8;  //50 cents coins
    available_coins[0].quant = 12; //100 cents coins


    if(((change/10 < 2)&&(change%10 != 0)) || (change/10 >= 2)&&((change%10 != 5) && change%10 != 0)) {
        printf("It was not possible to change the value\n");
        return 0;
    }
    else {
        for(int i=0; i<2; i++){
            changecoins[i] = change / available_coins[i].value;
            change = change % available_coins[i].value;
            if(changecoins[i] >= available_coins[i].quant) {
                change = change + (changecoins[i] - available_coins[i].quant) * available_coins[i].value;
                changecoins[i] = available_coins[i].quant;
            }
        }

        if(change%10 == 5) {
            if(available_coins[2].quant < 1) {
                printf("It was not possible to change the value\n");
                return 0;
            }
            else {
                changecoins[2] = change / available_coins[2].value;
                change = change % available_coins[2].value;
                if(changecoins[2] >= available_coins[2].quant) {
                    change = change + (changecoins[2] - available_coins[2].quant) * available_coins[2].value;
                    changecoins[2] = available_coins[2].quant;
                }
                if(change%10 == 5) {
                    changecoins[2]--;
                    change = change + available_coins[2].value;
                }
            }
        }

        changecoins[3] = change / available_coins[3].value;
        change = change % available_coins[3].value;
        if(changecoins[3] >= available_coins[3].quant) {
            change = change + (changecoins[3] - available_coins[3].quant) * available_coins[3].value;
            changecoins[3] = available_coins[3].quant;
        }

        if(change>0) {
            printf("It was not possible to change the value\n");
        }
        else {
            printf("Change:\n");
            printf("\t%d 100 cent coin(s).\n", changecoins[0]);
            printf("\t%d 50 cent coin(s).\n", changecoins[1]);
            printf("\t%d 25 cent coin(s).\n", changecoins[2]);
            printf("\t%d 10 cent coin(s).\n", changecoins[3]);

            for(int i = 0; i < 4; i++) {
                available_coins[i].quant -= changecoins[i];
            }
        }
    }
    return 0;
}

硬币找零算法C

Coin Change Algorithm C

c

algorithm

coin-change