Как узнать, создал я жадный алгоритм или нет?

Question

Я читал, что жадный алгоритм заботится только об оптимальном решении, которое пытается достичь в данный момент, но является ли это единственным критерием, который я должен учитывать, если я хочу создать жадный алгоритм? Также, как я могу знать, создал ли я жадный алгоритм или нет? Я имею в виду, я создал следующий код для проблемы изменения в C++:

#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

Да, это жадно - вы берете как можно больше первой деноминации, затем как можно больше следующей и т. Д.

Однако есть несколько проблем.

Самая важная проблема заключается в том, что ваша функция будет работать только один раз из-за локальной переменной * stati c. (Изменяемое состояние и рекурсия не являются приятной комбинацией.)

Вы можете решить эту проблему, также передав текущий индекс в качестве аргумента, но вместо этого я бы изменил массив и go в обратном направлении.

Вторая проблема - небольшая неэффективность с этим l oop:

    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;
}

Answer 2

Да, это жадно.

Однако есть 2 проблемы.

Во-первых, вместо l oop, вы должны были использовать простое деление:

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

может быть легко заменено на:

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

Во-вторых, ваша программа использует рекурсию с переменной stati c - обычно это вызывает недовольство. Вы должны заменить это простым l oop over i вместо рекурсивного вызова.