जावा एक 2D सरणी

Question

के माध्यम से रास्ते में अधिकतम राशि मूल रूप से मैं एक समस्या यह है कि यह करने के लिए कुछ इसी तरह से चला जाता है की है। प्रत्येक पौधे (प्रत्येक तत्व) में कई स्ट्रॉबेरी होती है। आप सरणी के ऊपरी बाएं कोने में शुरू करते हैं, और आप केवल दाएं या नीचे जा सकते हैं। मुझे बगीचे के माध्यम से पथों की गणना करने के लिए एक पुनरावर्ती विधि तैयार करने की आवश्यकता है और फिर उत्पादन जो सबसे अधिक स्ट्रॉबेरी पैदा करता है।

मुझे लगता है कि मुझे वास्तव में वास्तव में सरल रिकर्सन समस्याओं की समझ है, लेकिन यह समस्या मेरे सिर पर चली गई है। मुझे सच में यकीन नहीं है कि कहां से शुरू करना है या जहां तक ​​एक रिकर्सिव विधि बनाना है।

कोड से संबंधित कोई भी मदद या इस समस्या के पीछे अवधारणा को समझने में मेरी सहायता करने की बहुत सराहना की जाती है। धन्यवाद।

Answer 1

दासब्लिंकनलाइट की तरह, यह करने का सबसे प्रभावी तरीका एक ज्ञापन या गतिशील प्रोग्रामिंग तकनीक का उपयोग कर रहा है। मैं गतिशील प्रोग्रामिंग पसंद करते हैं, लेकिन मैं यहां शुद्ध रिकर्सन का उपयोग करूंगा।

उत्तर एक मौलिक प्रश्न के उत्तर के आसपास केंद्र है: "यदि मैं अपने क्षेत्र में पंक्ति आर और कॉलम सी में वर्ग में हूं, तो मैं यहां बाईं ओर से पथ का मूल्यांकन कैसे कर सकता हूं जैसे कि संख्या स्ट्रॉबेरी अधिकतम है? "

एहसास करने की कुंजी यह है कि पंक्ति आर और कॉलम सी में साजिश में आने के केवल दो तरीके हैं: या तो मैं ऊपर से वहां जा सकता हूं, पंक्ति आर -1 और कॉलम सी में साजिश का उपयोग करके, या मैं प्राप्त कर सकता हूं पंक्ति आर और कॉलम सी -1 में साजिश का उपयोग करके, तरफ से।

int[][] field;  
int max(int r, int c) { 
    //Base case 
    if (r == 0 && c == 0) { 
     return field[r][c]; 
    } 
    //Assuming a positive number of strawberries in each plot, otherwise this needs 
    //to be negative infinity 
    int maxTop = -1, maxLeft = -1; 
    //We can't come from the top if we're in the top row 
    if (r != 0) { 
     maxTop = field[r-1][c]; 
    } 
    //Similarly, we can't come from the left if we're in the left column 
    if (c != 0) { 
     maxLeft = field[r][c-1]; 
    } 
    //Take whichever gives you more and return.. 
    return Math.max(maxTop, maxLeft) + field[r][c]; 
} 

कॉल अधिकतम (आर -1, सी -1) के लिए: उसके बाद, आप बस सुनिश्चित करें कि आप अपने आधार मामलों पता है ... जिसका अर्थ है की तरह कुछ, मौलिक रूप से, मेरे विशुद्ध रूप से पुनरावर्ती संस्करण होगा बनाने की जरूरत है अपना जवाब प्राप्त करें। ध्यान दें कि यहां बहुत अक्षमता है; आप गतिशील प्रोग्रामिंग (जो मैं नीचे प्रदान करूंगा) या ज्ञापन (जिसे पहले ही परिभाषित किया गया है) का उपयोग करके बहुत बेहतर करूँगा। हालांकि, याद रखने की बात यह है कि डीपी और ज्ञापन तकनीक दोनों ही अधिक कुशल तरीके हैं जो यहां उपयोग किए जाने वाले पुनरावर्ती सिद्धांतों से आती हैं।

डी पी:

int maxValue(int[][] field) { 
    int r = field.length; 
    int c = field[0].length; 
    int[][] maxValues = new int[r][c]; 
    for (int i = 0; i < r; i++) { 
     for (int j = 0; j < c; j++) { 
      if (i == 0 && j == 0) { 
       maxValues[i][j] = field[i][j]; 
      } else if (i == 0) { 
       maxValues[i][j] = maxValues[i][j-1] + field[i][j]; 
      } else if (j == 0) { 
       maxValues[i][j] = maxValues[i-1][j] + field[i][j]; 
      } else { 
       maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j]; 
      } 
     } 
    } 
    return maxValues[r-1][c-1]; 
} 

दोनों ही मामलों में, यदि आप वास्तविक पथ से बनाना चाहते हैं, बस बूलियन्स कि साथ मेल खाती है की एक 2D तालिका रखना "मैं ऊपर या बाईं ओर से आया था?" यदि सबसे स्ट्रॉबेरी पथ ऊपर से आता है, तो सही रखें, अन्यथा झूठी डालें। इससे आपको गणना के बाद पैच को पुनः प्राप्त करने की अनुमति मिल सकती है।

ध्यान दें कि यह अभी भी प्रिंसिपल में रिकर्सिव है: प्रत्येक चरण में, हम अपने पिछले परिणामों पर वापस देख रहे हैं। हम अपने पिछले परिणामों को कैशिंग करते हैं, इसलिए हम काम का एक गुच्छा बर्बाद नहीं करते हैं, और हम एक बुद्धिमान क्रम में उपप्रोबम पर हमला कर रहे हैं ताकि हम उन्हें हमेशा हल कर सकें। गतिशील प्रोग्रामिंग पर अधिक जानकारी के लिए, Wikipedia देखें।

Answer 2

आप इसे memoization का उपयोग करके कर सकते हैं। यहां जावा-जैसे छद्मोडोसे (memo, R है, और Cmax विधि के लिए उदाहरण चर उपलब्ध हैं) माना जाता है।

int R = 10, C = 20; 
int memo[][] = new int[R][C]; 
for (int r=0 ; r != R ; r++) 
    for (int c = 0 ; c != C ; c++) 
     memo[r][c] = -1; 
int res = max(0, 0, field); 

int max(int r, int c, int[][] field) { 
    if (memo[r][c] != -1) return memo[r][c]; 
    int down = 0; right = 0; 
    if (r != R) down = max(r+1, c, field); 
    if (c != C) right = max(r, c+1, field); 
    return memo[r][c] = (field[r][c] + Math.max(down, right)); 
} 

Answer 3

आप इसे डीपी सारणीकरण विधि के साथ हल कर सकते हैं, जिसके साथ आप ओ (एम * एन) से केवल ओ (एन) तक स्थान बचा सकते हैं। डीपी याद करने के साथ, आपको मध्यवर्ती मूल्यों को स्टोर करने के लिए एम * एन मैट्रिक्स की आवश्यकता है। मेरा पायथन कोड निम्नलिखित है। उम्मीद है कि यह मदद कर सकता है।

def max_path(field): 
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)] 
    for i in range(1, len(field)): 
     for j in range(len(dp)): 
      dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j] 
    return dp[-1]