दी गई मान बनाने वाले सिक्कों की न्यूनतम संख्या

सिक्कों की एक सूची C(c1, c2, ... Cn) दी गई है और एक मान V भी दिया गया है। अब समस्या मान V बनाने के लिए न्यूनतम संख्या में सिक्कों का उपयोग करना है।

नोट: मान लें कि सिक्कों C की अनंत संख्या है।

इस समस्या में, हम अलग-अलग सिक्कों का एक सेट C{1, 2, 5, 10} मानते हैं, प्रत्येक प्रकार के सिक्कों की अनंत संख्या है। अनुरोधित मान को बदलने के लिए हम किसी भी प्रकार के न्यूनतम सिक्के लेने का प्रयास करेंगे। उदाहरण के लिए, मान 22 के लिए: हम {10, 10, 2} चुनेंगे, न्यूनतम 3 सिक्के।

इनपुट और आउटपुट

इनपुट: आवश्यक मान। मान लें 48
आउटपुट: न्यूनतम आवश्यक सिक्के। यहां आउटपुट 7 है।
48 = 10 + 10 + 10 + 10 + 5 + 2 + 1

एल्गोरिदम

minCoins(coinList, n, value)

इनपुट: विभिन्न सिक्कों की सूची, सिक्कों की संख्या, दिया गया मान
आउटपुट: दिए गए मान को प्राप्त करने के लिए न्यूनतम सिक्कों की संख्या

शुरुआत
    यदि value = 0, तो
        वापस 0
    coins ऐरे को आकार value + 1 का परिभाषित करें, ∞ से भरें
    coins[0] := 0
    i := 1 से value तक, करें
        j := 0 से n तक, करें
            यदि coinList[j] <= i, तो
                tempCoins := coins[i-coinList[j]]
                यदि tempCoins ≠ ∞ और (tempCoins + 1) < coins[i], तो
                    coins[i] := tempCoins + 1
        पूर्ण
    पूर्ण
    वापस coins[value]
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int minCoins(int coinList[], int n, int value) {
    int coins[value+1];
    
    if(value == 0)
        return 0;
    
    coins[0] = 0;
    for (int i = 1; i <= value; i++)
        coins[i] = INT_MAX;
    
    for (int i = 1; i <= value; i++) {
        for (int j = 0; j < n; j++)
            if (coinList[j] <= i) {
                int tempCoins = coins[i-coinList[j]];
                if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
                    coins[i] = tempCoins + 1;
            }
    }
    return coins[value];
}

int main() {
    int coins[] = {1, 2, 5, 10};
    int n = 4, value;
    cout << "Enter Value: "; cin >> value;
    cout << "Minimum " << minCoins(coins, n, value) << " coins required.";
    return 0;
}

आउटपुट

Enter Value: 48
Minimum 7 coins required.