算法的最小變化量

Question

是的我知道有類似的帖子，但通過他們看後，我仍然卡住，因爲我很新的編程，沒有給出的答案是足夠具體的我的問題來幫助。

---

問題。 編寫一個高效的ACL（算法計算機語言）算法，給定一個項目的成本（小於或等於一美元），給出購買者50美分，20美分，10美分，5美分和1美分硬幣的數量如果他們交了一美元就會收到。您必須儘量減少更改中的硬幣數量。

---

問題是不與任何具體的編程語言，答案只能用簡單的ACL語言一樣，如果，如果其他，while循環而不能使用數組或其他高級命令。

這是我在這裏：

輸入代碼在這裏改變

{ 
    int cost, fifty, twenty, ten, five, one; 

    fifty = 0; 
    twenty = 0; 
    ten = 0; 
    five = 0; 
    one = 0; 

    read (cost); 
    if (cost <= 50) 
    { 
     fifty = 1; 

的算法最小量

---

完成的代碼，謝謝你們的幫助！如果您看到任何含糊之處或可以幫助我簡化代碼，請讓我知道。

---

Algorithm how much change 
{ 
    int cost, change, fifty, twenty, ten, five, one; 

    fifty = 0; 
    twenty = 0; 
    ten = 0; 
    five = 0; 
    one = 0; 

    read (cost); 
    change = 100 - cost; 

    if (change >= 50) 
    { 
     fifty = fifty + 1; 
     change = change - 50; 
    } 
    while (change >= 20) 
    { 
     twenty = twenty + 1; 
     change = change - 20; 
    } 
    while (change >= 10) 
    { 
     ten = ten + 1; 
     change = change - 10; 
    } 
    while (change >= 5) 
    { 
     five = five + 1; 
     change = change - 5; 
    } 
    while (change >= 1) 
    { 
     one = one + 1; 
     change = change - 1; 
    } 

    print(one, five, ten, twenty, fifty); 
} 

Answer 1

實際上，成本> =要（超過1美元的情況下）只檢查一次50需要，但是這是比較通用的

while (cost >= 50) 
{ 
fifty++; 
cost -= 50; 
} 
while (cost >= 20) 
{ 
twenty++; 
cost -=20; 
} 
... 

Answer 2

因爲這聽起來像功課我不會馬上給出答案，但給你一個正確的方向提示。

假設你是程序中的某一點。你有一定的金額返回，比方說80美分。你會如何去得到一個硬幣，你肯定必須返回？

Answer 3

對於您的特定更改金額，我相信一個簡單的貪婪天真的「挑選最大的，直到我不能再」策略將工作。

例：

1. 我多少50的可50年代的量前挑比變化量更大？跟蹤這個數字50年代的，從總
2. 重複了20年代，10的減去金額等

然而，它並不總是遵循貪心方法會奏效。對於「一般」解決方案，請參閱Coin Change - Algorithmist

Answer 4

提示：從最大的硬幣開始，找出可以使用的硬幣的最大數量，然後轉到第二大硬幣並重復。看起來他們通過使用二十個硬幣而不是二十五個哈利來讓你更容易。

Answer 5

more detailed: 

and even a brute force algorithm which is O(d M^d) 

This is fromMax Alekseyev, University of South Carolina cse。