गतिशील प्रोग्रामिंग - सी

Question

में सिक्कों की न्यूनतम संख्या मैंने साइट पर विभिन्न प्रश्नों को देखा है और मैंने निम्न तर्क से इसे लागू करने में कुछ भी नहीं ढूंढ पाया है (इसलिए मुझे उम्मीद है कि यह डुप्लिकेट नहीं है)।

एक वेंडिंग मशीन नियंत्रक आपके कि आवश्यक परिवर्तन बनाने के सिक्कों की न्यूनतम संख्या की गणना करने के लिए आवश्यक हैं के प्रोग्रामर के रूप में:

समस्या मैं एक सी कार्यक्रम के माध्यम से हल करने के लिए कोशिश कर रहा हूँ

पीछा कर रहा है ग्राहकों को वापस देने के लिए। इस समस्या का एक कुशल समाधान एक गतिशील प्रोग्रामिंग दृष्टिकोण लेता है, जिसमें 1 सेंट परिवर्तन के लिए आवश्यक सिक्कों की संख्या की गणना करना शुरू होता है, फिर 2 सेंट के लिए, फिर 3 सेंट के लिए, आवश्यक परिवर्तन तक पहुंचने तक और प्रत्येक बार पूर्व गणना का उपयोग करने तक सिक्कों की संख्या। फ़ंक्शन ComputeChange() युक्त एक प्रोग्राम लिखें, जो वैध सिक्के और आवश्यक परिवर्तन की एक सूची लेता है। इस कार्यक्रम को बार-बार कंसोल से आवश्यक परिवर्तन के लिए पूछना चाहिए और तदनुसार ComputeChange() पर कॉल करना चाहिए। इसे "कैशिंग" का भी उपयोग करना चाहिए, जहां किसी भी पहले गणना की गई मध्यवर्ती मानों को बाद के लुक-अप के लिए बनाए रखा जाता है।

कौन सा मैं पर मेरी कोड के आधार पर करने की कोशिश की:

कैसे दूसरों को इसे हल है खोजने के लिए ऑनलाइन चारों ओर देखने के बाद, मैं निम्न उदाहरण पैसे, nickels और ऑफ डाइम्स के साथ लागू पाया। लेकिन सबसे पहले, मेरा कोड रोक नहीं रहा है, और दूसरी बात, मुझे यकीन नहीं है कि क्या मैं उपरोक्त रूब्रिक में वर्णित कैशिंग तत्व शामिल कर रहा हूं। (मुझे सच में यकीन नहीं है कि मुझे उस हिस्से के बारे में कैसे जाना है)।

क्या कोई मेरे कोड में त्रुटियों को ढूंढने में मदद कर सकता है?

#include <stdio.h> 
#include <limits.h> 

int computeChange(int[],int,int); 
int min(int[],int); 

int main(){ 
    int cur[]={1,2,5,10,20,50,100,200}; 
    int n = sizeof(cur)/sizeof(int); 
    int v; 

    printf("Enter a value in euro cents: "); 
    scanf("%d", &v); 

    printf("The minimum number of euro coins required is %d", computeChange(cur, v, n)); 

    return 0; 
} 

int computeChange(int cur[], int v, int n){ 
    if(v < 0) 
     return -1; 
    else if(v == 0) 
     return 0; 
    else{ 
     int possible_mins[n], i; 
     for(i = 0; i < n; i++){ 
      possible_mins[i]=computeChange(cur, v-cur[i], n); 
     } 
     return 1+min(possible_mins, n); 
    }; 
} 

int min(int a[], int n){ 
    int min = INT_MAX, i; 
    for(i = 0; i < n; i++){ 
     if((i>=0) && (a[i]< min)) 
      min = a[i]; 
    } 
    return min; 
} 

किसी भी सहायता की सराहना की जाएगी।

Answer 1

ओपी के आपूर्ति Change() एल्गोरिथ्म बहुत प्रत्यावर्तन की पड़ता है, यहां तक ​​कि if(v < 0) return INT_MAX; सुधार के साथ। इतने सारे रिकर्सन कि छोटे-छोटे मूल्य भी लाखों रिकर्सिव कॉल लेते हैं।

एक सरल सुधार अब तक का सबसे अच्छा समाधान "कैश" करना है। फिर जब एक मध्यवर्ती समाधान सबसे अच्छा से पहले से भी बदतर है, तो उस पथ को जारी रखने की कोई आवश्यकता नहीं है।

int computeChange(int cur[], int v, int n, int count_now, int *bestcount) { 
    if (count_now >= *bestcount) { 
    return INT_MAX; 
    } 
    if (v < 0) { 
    return INT_MAX; 
    } 
    if (v == 0) { 
    *bestcount = count_now; 
    return 0; 
    } 

    int min_count = INT_MAX; 
    for (int i = 0; i < n; i++) { 
    int count = computeChange(cur, v - cur[i], n, count_now+1, bestcount); 
    if (count < min_count) { 
     min_count = count + 1; 
    } 
    } 
    return min_count; 
} 

    int bc = INT_MAX; 
    computeChange(cur, v, n, 0, &bc)); 

एक माध्यमिक सुधार करता है, तो आप में से कहते हैं एक्स राशि है और मूल्यवर्ग के सिक्के a1, a2, a3, a4.. कहना (घटते क्रम में) पहली

// int count = computeChange(cur, v - cur[i], n, count_now+1, bestcount); 
int count = computeChange(cur, v - cur[n-i-1], n, count_now+1, bestcount); 

Answer 2

तो नीचे ज्ञापन और गतिशील प्रोग्रामिंग का उपयोग करके आपकी समस्या के लिए कोड स्निपेट नीचे दिया गया है। जटिलता ओ है (वैल * numTypesof सिक्के)।

अंत में, बदलें [वैल] आपको वैल के लिए सिक्के की न्यूनतम संख्या देगा।

int change [MAX]; 
int cur[]={1,2,5,10,20,50,100,200}; 
int n = sizeof(a)/sizeof(int); 
int val= //whatever user enters to get the num of coins required. 

for (i=0; i <= val; i++) { 
    change[i] = INT_MAX; 
} 
for (i=0; i < n; i++) { // change for the currency coins should be 1. 
    change[cur[i]] = 1; 
} 

for (i=1; i <= val; i++) { 
    int min = INT_MAX; 
    int coins = 0; 
    if (change[i] != INT_MAX) { // Already got in 2nd loop 
     continue; 
    } 
    for (j=0; j < n; j++) { 
     if (cur[j] > i) { // coin value greater than i, so break. 
      break; 
     } 
     coins = 1 + change[i - cur[j]]; 
     if (coins < min) { 
      min = coins; 
     } 
    } 
    change[i] = min; 

} 

Answer 3

बड़े सिक्के का उपयोग कर प्रयास करने के लिए तो जवाब बस है -> x/a1+(x%a2)/a3+((x%a2)%a3)/a4+... यह उम्मीद है कि उत्तर