सिक्का परिवर्तन के लिए अंतरिक्ष अनुकूलित समाधान

Question

यदि हम एन सेंट के लिए परिवर्तन करना चाहते हैं, तो हमारे मूल्य एन को देखते हुए, और हमारे पास एस = {एस 1, एस 2, .., एसएम} मूल्यवान सिक्कों में से प्रत्येक की असीमित आपूर्ति है, कितने तरीके क्या हम बदलाव कर सकते हैं? सिक्कों का आदेश कोई फर्क नहीं पड़ता।

उदाहरण के लिए, एन = 4 और एस = {1,2,3} के लिए, चार समाधान हैं: {1,1,1,1}, {1,1,2}, {2,2} , {1,3}। तो उत्पादन होना चाहिए 4. एन = 10 और एस = {2, 5, 3, 6} के लिए, पांच समाधान हैं: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} और {5,5}। तो आउटपुट होना चाहिए 5.

मुझे 3 दृष्टिकोण HERE मिला। लेकिन स्पेस अनुकूलित गतिशील प्रोग्रामिंग दृष्टिकोण को समझने में सक्षम नहीं है, जहां केवल एक ही आयामी सरणी तालिका [] का उपयोग किया जाता है।

int count(int S[], int m, int n) 
{ 
    // table[i] will be storing the number of solutions for 
    // value i. We need n+1 rows as the table is consturcted 
    // in bottom up manner using the base case (n = 0) 
    int table[n+1]; 

    // Initialize all table values as 0 
    memset(table, 0, sizeof(table)); 

    // Base case (If given value is 0) 
    table[0] = 1; 

    // Pick all coins one by one and update the table[] values 
    // after the index greater than or equal to the value of the 
    // picked coin 
    for(int i=0; i<m; i++) 
     for(int j=S[i]; j<=n; j++) 
      table[j] += table[j-S[i]]; 

    return table[n]; 
} 

Answer 1

सबसे पहले ध्यान दें कि तालिका [i] सिक्का बदलाव के लिए तरीके जब एन = मैं की संख्या है।

दिया गया एल्गोरिदम सिक्का (एस []) के अनुसार इस सरणी (तालिका []) को भरता है। प्रारंभ में तालिका [] में सभी मान 0 से शुरू किए गए हैं और तालिका [0] 0 पर सेट है (यह मूल मामला एन = 0 है)।

प्रत्येक सिक्का निम्नलिखित तरीके से तालिका [] में मूल्य जोड़ता है।

1. तालिका [X] = तालिका [X] + 1

   यह समझने में आसान है -

   मूल्य एक्स के सिक्के के लिए, निम्न तालिका [] को अपडेट कर रहे हैं। विशेष रूप से यह समाधान जोड़ता है {एक्स}।

2. सभी Y> एक्स

   तालिका [Y] = तालिका [Y] तालिका [वाई X]

   यह समझने के लिए मुश्किल है के लिए । उदाहरण एक्स = 3 लें, और वाई = 4.

   4 = 3 + 1 यानी 4 को 3 और 1 के संयोजन से प्राप्त किया जा सकता है और 1 प्राप्त करने के तरीकों की परिभाषा संख्या तालिका [1] है। ताकि तालिका में कई तरीकों को जोड़ा जा सके [4]। Thats क्यों ऊपर अभिव्यक्ति तालिका [वाई-एक्स] का उपयोग करता है।

अपने एल्गोरिथ्म में निम्न पंक्ति में एक ही प्रतिनिधित्व करता (दो कदम ऊपर) -

table[j] += table[j-S[i]]; 

एल्गोरिथ्म के अंत में, मेज [n] n के लिए समाधान में शामिल है।

Answer 2

इस तरह से एल्गोरिदम को समझने का प्रयास करें।

table[i][j] मूल्य j के लिए परिवर्तन करने के लिए पहले i प्रकार के सिक्के का उपयोग करना है। तो:

table[i][j] = table[i-1][j] + table[i][j-S[i]]

जाहिर है जब j सिक्के को बनाने, आपके पास दो विकल्प। ith सिक्का का उपयोग नहीं कर रहे हैं या ith सिक्का का उपयोग नहीं कर रहे हैं। Ith सिक्का का उपयोग नहीं करते समय, समाधान संख्या table[i-1][j] है। Ith सिक्का का उपयोग करते समय, समाधान संख्या table[i][j-S[i]] है, जिसका अर्थ है जेएस [i] मान बनाने के लिए पहले I सिक्के का उपयोग करना। इसलिए, कुल मिलाकर दोनों का योग है, जो table[i-1][j] + table[i][j-S[i]]

कोड में, आप लूप के लिए देखेंगे। बाहरी लूप I और आंतरिक लूप पर जेनरेट करते हैं। += कथन उपरोक्त समीकरण के आधार पर table[i][j] की गणना करता है।

संपादित

table[j] अपने कोड में वास्तव में table[i][j] मैं ऊपर बात कर रहा हूँ और i अपने पाश में मूल्य है। लूप table[N] के बाद table[M][N] का अर्थ है, M सिक्कों का उपयोग करके, N के लिए मूल्य बनाने के लिए सभी सिक्के हैं।

मैं और अधिक विस्तार कोड के आधार पर प्रदान करेगा:

for(int i=0; i<m; i++) 
     for(int j=S[i]; j<=n; j++) 
      table[j] += table[j-S[i]]; 

जब i = 0, table[j] पहले 1 सिक्के का उपयोग कर मूल्य j के लिए परिवर्तन करने के लिए इसका मतलब है। उदाहरण के लिए, table[2] अभी 2. तो के लिए परिवर्तन करने के लिए coins {1} का उपयोग कर का अर्थ है:

table[1] = table[1] + table[1 - S[0]] = table[1] + table[0] = 1 + 0= 1 
table[2] = table[2] + table[2 - S[0]] = table[2] + table[1] = 0 + 1= 1 
table[3] = 1 
table[4] = 1 

उसके बाद, हम परिणाम मिल गया जब मैं = 0. table[1] ~ table[4] अब मान 1, 2 के लिए परिवर्तन करने के लिए coin {1} का उपयोग कर का मतलब है, 3, 4 अलग से।

जब मैं = 1, table[j] का मतलब coin {1, 2} का उपयोग j के लिए परिवर्तन करने के लिए करता है।

table[2] = table[2] + table[2 - S[1]] = table[2] + table[0] = 1 + 1= 2 
table[3] = table[3] + table[3 - S[1]] = 1 + 1 = 2 
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3 

निम्न प्रक्रिया समान है।

अंत में, हम table[4] ले जब i = 1 बाहर है और यह विश्लेषण:

table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3 

यहाँ table[4] बाईं तरफ के मूल्य हम गणना कर रहे हैं और वास्तव में यह table[i=1][4] है। दाईं ओर table[4] पिछले मान का प्रतिनिधित्व करता है और इस मामले में, table[i=0][4]। यह विस्तार कर सकता है:

table[i=1][4] = table[i=0][4] + table[i=1][4 - S[1]] 

समीकरण ठीक है

table[i][j] = table[i-1][j] + table[i][j-S[i]] 

संपादित करें पालन-अप प्रश्न

आपको लगता है कि आप वास्तव में इस सवाल को समझते हैं, एक नए के साथ एक ही समस्या का समाधान करने का प्रयास करें बाधा। क्या होगा यदि हर सिक्का का उपयोग केवल एक बार किया जा सकता है? उदाहरण के लिए, एन = 4 और एस = {1,2,3}, केवल एक समाधान {1,3} ताकि आउटपुट 1 होना चाहिए। और एन = 10 और एस = {2, 5, 3, 6} के लिए, अभी भी केवल एक समाधान {2, 3, 5} और आउटपुट 1.

संकेत: मूल कोड का केवल एक पंक्ति परिवर्तन पर्याप्त है।

उत्तर: http://ideone.com/t1JnEz