C प्रोग्राम: कॉइन चेंज समस्या

कॉइन चेंज समस्या क्या है?

इस समस्या में, हमें एक मान n दिया जाता है, और हमें n रुपये का चेंज बनाना होता है। हमारे पास m मूल्य के सिक्के होते हैं (1 से m तक)। हमें उन सभी संभावित तरीकों की कुल संख्या लौटानी होती है जिनसे हम दी गई राशि का योग बना सकते हैं।

उदाहरण

इनपुट: N = 6, सिक्के = {1, 2, 4}
आउटपुट: 6
व्याख्या: 6 का योग बनाने वाले संयोजन हैं:
{1,1,1,1,1,1}, {1,1,1,1,2}, {1,1,2,2}, {1,1,4}, {2,2,2}, {2,4}

C प्रोग्राम कार्यान्वयन

#include <stdio.h>

int coins(int S[], int m, int n) {
    int i, j, x, y;
    int table[n+1][m];

    for (i = 0; i < m; i++)
        table[0][i] = 1;

    for (i = 1; i < n+1; i++) {
        for (j = 0; j < m; j++) {
            x = (i - S[j] >= 0) ? table[i - S[j]][j] : 0;
            y = (j >= 1) ? table[i][j-1] : 0;
            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}

int main() {
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf("सिक्कों के कुल संयोजन जो %d का योग बनाते हैं: %d", n, coins(arr, m, n));
    return 0;
}

आउटपुट

सिक्कों के कुल संयोजन जो 4 का योग बनाते हैं: 4

एल्गोरिदम समझाया गया

यह एक डायनामिक प्रोग्रामिंग दृष्टिकोण है। हम एक 2D टेबल बनाते हैं जहां table[i][j] पहले j सिक्कों का उपयोग करके राशि i बनाने के तरीकों की संख्या संग्रहीत करता है।

• बेस केस: राशि 0 को बनाने का 1 तरीका होता है (कोई सिक्का न चुनकर)।
• पुनरावृत्ति: प्रत्येक राशि और सिक्के के लिए, हम दो विकल्पों पर विचार करते हैं:
  1. वर्तमान सिक्के को शामिल करें: table[i - S[j]][j]
  2. वर्तमान सिक्के को बाहर करें: table[i][j-1]
• अंतिम उत्तर table[n][m-1] में होता है।

जटिलता विश्लेषण

• समय जटिलता: O(n × m)
• स्थान जटिलता: O(n × m)

नोट: स्थान को O(n) तक अनुकूलित किया जा सकता है 1D सरणी का उपयोग करके।