如何知道我是否创建了贪婪算法？

2024-05-20 • 问答

我已经读到，贪心算法只关心当时试图达到的最佳解决方案，但是如果我要创建贪心算法，这是我应该考虑的唯一标准吗？ Aslo，我怎么知道我是否创建了贪婪算法？我的意思是，我为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,money)<<endl;
    return 0;
}

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

是的，这是贪婪的。

但是有两个问题。

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

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

可以很容易地替换为：

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

第二，您的程序使用带有静态变量的递归-通常对此不满意。您应该用i上的简单循环代替它，而不是递归调用。

是的，这很贪心–您尽可能多地选择第一个面额，然后尽可能多地选择下一个面额，依此类推。

但是有两个问题。

最重要的问题是由于局部静态变量，您的函数只能运行一次。（可变状态和递归并不是一种令人愉快的组合。）

您也可以通过将当前索引作为参数来解决此问题，但是我会反转数组并向后退。

第二个问题是此循环的效率低下：

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

您可以用除法和乘法代替。

int greedyChange(int coinSet[],int index,int money){
    if(index < 0 || money <= 0){
        return 0;
    }
    int coins = money / coinSet[index];
    return coins + greedyChange(coinSet,index - 1,money - coins * coinSet[index]);
}


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

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

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

如何知道我是否创建了贪婪算法？

frankjzp12 回答：如何知道我是否创建了贪婪算法？

大家都在问