c - 我正在编写一个关于更改制作的蛮力算法，但我有点卡住了

Question

我需要编写一个程序，使用强力方法找出如何最有效地进行更改。我有点困惑，我很好奇我是否在正确的轨道上。我正在用 C 语言编写它。

它不使用贪心算法。

这只是让我感到困惑而已。最后它应该输出最有效的零钱，依次为 toonie、loonie、quarter、dimes、nickels、pennies。 (比如 1 1 0 0 1 0。)

我走在正确的轨道上吗？我对我在做什么有点困惑，六个 for 循环显然是关键，我在每次迭代中都添加了，但关于概念上发生的事情我有点困惑。

#include <stdio.h>

int main(int argc, char *argv[]) {
    //Input
    int amount = 336;
    int bestSolution = amount;
    //Coins
    int toonies = 0, loonies = 0, quarters = 0, dimes = 0, nickels = 0, pennies = 0;
    int amountAfterToonies, amountAfterLoonies, amountAfterQuarters, amountAfterDimes, amountAfterNickels;
    //Counters
    int i, j, k, l, m, n;

    for (i = 0; i < amount / 200; i++) { //Finds amount 
        toonies++;
        amountAfterToonies = amount % 200;
        for (j = 0; j < amountAfterToonies / 100; j++) {
            loonies++;
            amountAfterLoonies = amountAfterToonies % 100;
            for (k = 0; k < amountAfterLoonies / 25; k++) {
                quarters++;
                amountAfterQuarters = amountAfterLoonies % 25;
                for (l = 0; l < amountAfterQuarters / 10; l++) {
                    dimes++;
                    amountAfterDimes = amountAfterQuarters % 10;
                    for (m = 0; m < amountAfterDimes / 5; m++) {
                        nickels++;
                        amountAfterNickels = amountAfterDimes % 5;
                    for (n = 0; n < amountAfterNickels; n++) {
                        pennies++;
                        sum = toonies + loonies + quarters + dimes + nickels + pennies;
                        if (sum < bestSolution) {
                            bestSolution = sum;
                        }
                    }
                }
            }
        }
    }
}
printf("%d %d %d %d %d %d\n", toonies, loonies, quarters, dimes, nickels, pennies);
printf("%d\n", bestSolution);
return 0;
}

Answer 1

您找不到最有效的方法。你找到所有的方法。

我建议你这样:

toonies=amount/200;
amount%=200;
loonies=amount/100;
amount%=100;
//and so on

(即使你想保留循环，将它们分开 - 没有理由使用嵌套循环)