算法來計算100美元硬幣的價值是否可能

-1

明天我的兒子在上課的第100天必須帶上100分。我想用便士，但他說太多人在這樣做。有沒有一種動態編程算法可以讓我用100個硬幣產生所有美元值，包括美元硬幣？算法來計算100美元硬幣的價值是否可能

可接受的值爲1，5，10，25，100最大值爲10000

只是試圖讓我的兒子高興，並在同一時間提供一些知識類。任何幫助表示讚賞，我不想成爲只發送100便士的那位父親。這不是關於用最少數量的硬幣提供解決方案，更多的是提供具有確切數量的硬幣的解決方案。

2014-02-11 Chris.Stover

是真的是一個好主意，你的孩子送100美元的硬幣在學校？ – templatetypedef

他有一位好老師，她絕對會把所有的錢都寄回來。更重要的是，這不是關於金錢，而是關於讓我的兒子開心，並教他計算的價值。我可能會選擇一個接近10或25的數字。 –

@Vikram，不是僞造，我發佈了我的解決方案。在我的學校裏，沒有人會對這個算法感興趣，這太簡單了。如果我在這個週末記得這樣做，我就不會在這裏。對不起，如果你不相信我，但如果你讀了這篇文章，你會發現沒有人提供給我這個解決方案。我花了更多時間在SO上，發現了一些我可以修改的代碼以適應我的需求。 –

所以這裏是我最終使用的最終代碼。這是代碼的修改版本上的SO問題發現：

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

int main(int argc, char *argv[]) 
{ 
    int total = 100; 

    while (total < 2501){ 
     int combos = 0; 

     for (int q = 0; q <= total/25; q++) 
     { 
      int total_less_q = total - q * 25; 
      for (int d = 0; d <= total_less_q/10; d++) 
      { 
       int total_less_q_d = total_less_q - d * 10; 
       for (int n = 0; n <= total_less_q_d/5; n++) 
       { 
        int p = total_less_q_d - n * 5; 
        if((q+d+n+p) == 100){ 
         if(q < 9 && d < 14 && n < 5 && p < 100) { 
          printf("total: %d\t%d\t%d\t%d\t%d\n", 
            total, q, d, n, p); 
         } 
        } 
        combos++; 
       } 
      } 
     } 
     total++; 
    } 
    return 0; 
}

很抱歉，如果語法搞砸了，我還有其他的事情需要擔心今晚。我在房子裏的宿舍，硬幣，鎳幣和便士的數量都是硬編碼的，所以如果這些代碼會被重複使用，就會改變這些值。

來源

2014-02-11 06:45:03

它可以'手'完成。假設你有一組硬幣可以產生所有值高達V的值。它們可能會產生更大的值，但不會產生值V + 1。如果您將硬幣添加到具有值n < = V + 1的集合，則新集合可以生成所有達到V + n的值。有了這個問題，我們可以問什麼是我的套幣可以產生的最大連續值，並且對於下一個硬幣來選擇最大的硬幣是< = V + 1。

E.g.生產1，我們需要硬幣與價值1.如果我們沒有它，我們卡住:-)

{1} -> V=1 -> next coin is 1 
{2*1} -> V=2 -> next coin is 1 
{3*1} -> V=3 -> next coin is 1 
{4*1} -> V=4 -> next coin is 5 
{4*1, 5} -> V=9 -> next coin is 10 
{4*1, 5, 10} -> V=19 -> next coin is 10 
{4*1, 5, 2*10} -> V=29 -> next coin is 25 
{4*1, 5, 2*10, 25} -> V=54 -> next coin is 50 
...

來源

2014-02-11 08:27:38 Ante

算法來計算100美元硬幣的價值是否可能

回答

相關問題