c++ - 如何知道我是否创建了贪心算法？

Question

我读到过贪心算法只考虑当时试图达到的最优解，但如果我想创建一个贪心算法，这是我应该考虑的唯一标准吗？另外，我怎么知道我是否创建了贪心算法？我的意思是，我针对 C++ 中的change 问题创建了以下代码:

#include <iostream>

using namespace std;

int greedyChange(int coinSet[], int lenCoinSet,  int money){
    int change = 0;
    static int i = 0;

    if(i >= lenCoinSet){
        return 0;
    }
    while(money - coinSet[i] >= 0){
        change++;
        money -= coinSet[i];
    }
    i++;
    return change + greedyChange(coinSet, lenCoinSet, money);
}

int main(int argc, char const *argv[]){

    int coinSet[]={20, 15, 10, 5, 1};
    int lenCoinSet = sizeof(coinSet)/sizeof(coinSet[0]);
    int money = 30;

    cout << "The minimun number of coins to get your change is: " 
            << greedyChange(coinSet, lenCoinSet, money)<<endl;
    return 0;
}

而且我认为它是贪心的，但我不确定。如果您能解释我写的代码是否贪婪，我将不胜感激。此外，如果不是，您是否有其他可能的解决方案可以分享或者可能有一些建议来改进此代码？最后，如果有文档可以推荐给我，我将不胜感激。

Answer 1

是的，它很贪心。

但是有两个问题。

首先，您应该使用简单的除法而不是循环:

while(money - coinSet[i] >= 0){
    change++;
    money -= coinSet[i];
}

可以很容易地替换为:

coins = money / coinSet[i]
change += coins
money -= coins * coinSet[i]

其次，您的程序对静态变量使用递归——这通常是不受欢迎的。您应该将其替换为 i 上的简单循环，而不是递归调用。