0

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

它不使用贪心算法。

这只是让我感到困惑。最后，它应该输出最有效的零钱，依次为：toonie、loonie、25th、dimes、nicks、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;
}
4

4 回答 4

3

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

我建议你这样做：

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

（即使你想保留循环，也要把它们分开——没有理由使用嵌套循环）

于 2012-02-16T01:02:56.573 回答
0

该算法取决于“贪婪”算法是否有效。Greedy 在美国有效，我认为在加拿大有效，但不会有效，例如，如果有 15 美分或 3 美元的钞票。

对于“贪婪”，您取所收到的总零钱，反复减去最大的钞票/硬币，直到金额小于钞票/硬币的价值，然后撞到下一个较小的钞票/硬币。

有几种方法可以做到这一点，但它可以在两个嵌套循环和一个包含纸币/硬币值的数组中有效地完成。或者你可以有 N 个顺序循环，一个用于每个钞票/硬币值。在这种情况下，循环不会被嵌套。基本上，每个循环都是

while (amountDue >= bill_coin_values[i]) {
    bills_coins_to_dispense[i]++;
    amountDue -= bill_coin_values[i];
}

（当然，上面的循环可以用模块化划分来代替，但这在这个开发阶段会混淆问题。）

但是将该循环粘贴在一个循环中，该循环i通过值列表递增，并且您必须使用两个循环版本。

即，外循环将类似于：

int numSizes = 7;
int bill_coin_values[] = {200, 100, 50, 25, 10, 5, 1};
int bills_coins_to_dispense[7];
for (int i = 0; i < numSizes; i++) {
    bills_coins_to_dispense[i] = 0;
    <Above loop>
}
于 2012-02-16T01:05:10.550 回答
0

您的解决方案将找到所有可能的解决方案。

你说的最有效率是什么意思？

您需要添加的步骤是记录您认为是最有效的解决方案的任何内容，并将其作为最后的答案。

编辑- 更正；你在正确的轨道上，但如果你跟踪你第一次发布的逻辑，你会发现你永远不会添加便士。这是因为在您实际获得有效结果的第一次迭代中，amountAfterDimes / 5为 0，因此您永远不会添加任何便士，因此永远不会找到正确的答案。

您需要让您的搜索尝试每个硬币的 0 次，以使其下降到正确的答案。

于 2012-02-16T01:06:06.663 回答
0

也许是失眠症增加了 Loonies 和 Toonies ......但这太有趣了，不能回答......

#include <stdio.h>
struct coin {
   char *name;
   int     value;
   int     number;
};
#define NUMCOINS 7
int main(int argc, char *argv[]) {
   //Input
   int amount = 336;
   //Coins
   struct coin coins[NUMCOINS]={{"toonies", 200, 0},{"loonies",100,0},{ "four bit", 50,0},{ "two bit", 25,0},{"short bit",10,0},{ "nickels",5,0},{"pennies",1,0}};
   //Counters
   int i;

   for(i=0;i<NUMCOINS;i++)
     for (;amount >= coins[i].value; amount-=coins[i].value,coins[i].number++);

   for(i=0;i<NUMCOINS;i++)
     printf("%s %d \n",  coins[i].name, coins[i].number);


 return 0;
}
于 2012-02-16T04:48:36.923 回答