私は変更作成時にブルートフォースアルゴリズムをコーディングしていますが、ちょっと立ち往生しています

Question

私はブルートフォース方式を使って最も効率的に変更する方法を見つけるプログラムを書く必要があります。私はちょっと混乱しているし、もし私が正しい道を歩いているなら、私は好奇心が強い。私はC言語で書いています。

貪欲アルゴリズムは使用しません。

私はすべてが混乱しています。最終的には、toonie、loonie、quarter、dimes、nickels、penniesの順番で最も効率的な変更を出力する必要があります。 （1 1 0 0 1のように）

正しい軌道に乗っていますか？私は自分が何をしているのか少し混乱しています.6つのループは明らかに鍵です。私はそれぞれの反復を追加していますが、概念的に何が起こっているのかは少し混乱しています。

#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 

（あなたがループを維持したい場合でも、それらを分離 - ネストされたループを使用する理由はない）アルゴリズムがかどうかに依存

Answer 2

を「貪欲」アルゴリズムが機能します。欲張りは米国で働いていますが、私はカナダでは思っていますが、例えば15セントの作品や3ドルの手形があれば、うまくいかないでしょう。

"欲張り"の場合、受け取った変更の合計額を取って、最大の請求書/硬貨を引き下げて、その額が請求書/硬貨の額より少なくなるまで繰り返してから、次の小額の硬貨/硬貨に落とします。

いくつかの方法がありますが、2つのネストループとbill/coin値を含む配列で効率的に行うことができます。または、N個のシーケンシャルループを持つことができます。各ループは、各請求書/コインの値ごとに1つずつあります。この場合、ループはネストされません。基本的には、各ループは

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

だろう（もちろん、上記のループは、モジュラー部門と交換することができるが、それは一種の発展のこの段階で問題を混乱させる。）

しかし、中にそのループスティック値のリストからiをインクリメントするループで、2つのループバージョンが必要です。

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> 
} 

Answer 3

あなたのソリューションは、すべての可能な解決策を見つける：

すなわち、外側のループのようなものだろう。

最も効率的なことを意味しますか？

あなたが追加する必要があるステップは、最も効率的な解決策であると考えられるものを記録し、その答えとして最後に提示することです。

修正 - あなたは正しい軌道に乗っていますが、最初に投稿したロジックを追跡すると、ペニーを追加することは決してありません。これは、実際に有効な結果が得られる最初の反復ではamountAfterDimes/5が0なので、決してペニーを追加しないので、決して正しい答えを見つけることができないからです。

正しい答えに降りるために、各コインの0個を試してみる必要があります。

Answer 4

多分それは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; 
}