贪心算法返回的数量对于小值来说太大，但对于较大的值则不会

Question

我正在写一个贪心算法（这已经让我很头疼了）它输出最少数量的可以用于某种货币价值的硬币，我终于得到了我满意的代码，或者我想法。当输入值 .41 时，我返回 4 coins 这是正确的 - 但是，输入 .01 returns 2 coins 我不知道为什么。

// declare variable change_owed, num_coins, and input globally
float change_owed = 0;
float dollars;
int cents;
int num_coins;

int main(void)
{
    // makes sure the input is non-negative
    do
    {
        dollars = get_float("Change owed:\n");
        cents = round(dollars * 100);
    }
    while(cents <= 0);

    // begin checking 


        while(cents - 25 >= 0) // quarters
        {
            num_coins++; // number of coins used, to be printed later, is incremented
            cents = cents - 25; // coin is subtracted from total
        }
        while(cents - 10 >= 0) // dimes
        {
            num_coins++;
            cents = cents >= 10;
        }   
        while(cents - 5 >= 0) // nickels
        {
            num_coins++;
            cents = cents - 5;
        } 
        while(cents >= 0) // pennies
        {
            num_coins++;
            cents = cents - 1;
        } 

    printf("%i coins\n", num_coins);
}

Answer 1

主要问题（差一个硬币）：

while(cents >= 0) // pennies

应该是

while (cents - 1 >= 0) // or even better: while (cents >= 1)

还有一个错别字：

cents = cents >= 10;

应该是

cents = cents - 10; // or even better: cents -= 10;

Answer 2

据我所知你还没有初始化 num_coins

int num_coins = 0;

您使用 while 循环有什么原因吗？整数运算会更容易地做同样的事情。由于 cents 是一个整数，将它除以另一个整数将 return 只是整数部分（有效向下舍入）。

num_coins = cents / 25; // returns the integer part, count of quarters
                        // This is an alternative to initialization
cents %= 25; // modulus operator returns the remainder
num_coins = num_coins + cents / 10; // count of dimes
cents %= 10;
num_coins = num_coins + cents / 5; // count of nickles
cents %= 5;
num_coins += cents; // cents must equal number of pennies required.

好的，上面的代码我没有测试过，所以可能会有一些错误，但是你明白了。

贪心算法返回的数量对于小值来说太大，但对于较大的值则不会

Greedy algorithm is returning quanities too large for small values, but not larger values

c

while-loop

greedy