算法的最小变化量

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。