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

Question

के साथ समस्याएं मुझे गतिशील प्रोग्रामिंग को समझने में कठिनाइयां मिली हैं, इसलिए मैंने कुछ समस्याओं को हल करने का निर्णय लिया। मैं सबसे लंबे समय तक आम subsequence, नेप्सेक समस्या जैसी बुनियादी गतिशील एल्गोरिदम पता है, लेकिन मैं उन्हें पता है क्योंकि मैं उन्हें पढ़ा है, लेकिन मैं अपने :-(

उदाहरण हम प्राकृतिक संख्याओं का परिणाम को राशि के लिए पर कुछ के साथ नहीं आ सकती। हर नंबर हम धन या ऋण के साथ ले जा सकते हैं अंत में हम इस राशि का निरपेक्ष मान ली जाने वाली सभी परिणाम को न्यूनतम संभव परिणाम को पाने के लिए

in1:।।। 10 3 से 5 4; out1: 2

in2 : 4 11 5 5 5; आउट 2: 0

इन 3: 10 50 60 65 90 100; आउट 3: 5

तीसरे के लिए स्पष्टीकरण: 5 = | 10 + 50 + 60 + 65-90-100 |

इससे भी बदतर मेरे दोस्त ने मुझे बताया कि यह आसान knapsack समस्या है, लेकिन मैं यहां कोई भी knapsack नहीं देख सकता। गतिशील प्रोग्रामिंग कुछ मुश्किल है या केवल मुझे इसके साथ बड़ी समस्याएं हैं?

Answer 1

जैसा कि अमित द्वारा इंगित किया गया है, इस एल्गोरिदम को partition problem का उदाहरण माना जा सकता है। एक सरल कार्यान्वयन के लिए इस अजगर कोड पर एक नज़र डालें:

def partition(A): 
    n = len(A) 
    if n == 0: 
     return 0 
    k, s = max(A), sum(A)/2.0 
    table = [0 if x else 1 for x in xrange(n*k)] 
    for i in xrange(n): 
     for j in xrange(n*k-1, -1, -1): 
      if table[j-A[i]] > table[j]: 
       table[j] = 1 
    minVal, minIdx = float('+inf'), -1 
    for j in xrange(int(s)+1): 
     if table[j] and s-j < minVal: 
      minVal, minIdx = s-j, j 
    return int(2*minVal) 

जब प्रश्न में आदानों से एक के साथ कहा जाता है:

partition([10, 50, 60, 65, 90, 100]) 

यह 5 वापस आ जाएगी, अपेक्षा के अनुरूप। समाधान के पीछे गणित को पूरी तरह से समझने के लिए, कृपया इस examples पर एक नज़र डालें और "संतुलित विभाजन" लिंक पर क्लिक करें।

Answer 2

इस रस्साकशी में के रूप में एक ही समस्या है, संतुलित टीम आकार के बाधा (जो प्रासंगिक नहीं है) के बिना: http://acm.uva.es/p/v100/10032.html

मैं एक ऊपर से नीचे दृष्टिकोण के साथ इस समस्या का समाधान कर दिया था। यह बाधा पर काम करता है कि दिए गए नंबरों की ऊपरी सीमा है। क्या आपके पास ऊपरी सीमा है या संख्याएं अनियंत्रित हैं? अगर वे अनजान हैं तो मुझे नहीं लगता कि गतिशील प्रोग्रामिंग के साथ इसे कैसे हल किया जाए।

Answer 3

प्रत्येक तत्व के लिए यहां knapsack weight = value = number है।

आपकी बाध्य W1/2 * sum(elements) है।

विचार यह है कि - 1/2 * sum(elements) की सीमा पारित किए बिना आप "लेने" की संख्या को अधिकतम करना चाहते हैं, जो वास्तव में value=weight के साथ knapsack है।

यह समस्या वास्तव में partition problem है, जो subset sum problem का एक विशेष मामला है।

विभाजन समस्या कहती है: "क्या उन तत्वों का सबसेट प्राप्त करना संभव है जो वास्तव में आधा है?"
यहां से आपकी समस्या का व्युत्पन्न सरल है - यदि ऐसा है, तो इन्हें + के रूप में लें, और जिन्हें आपने - नहीं लिया है, और आपको out = 0 मिलते हैं। [दूसरी तरफ वही काम करता है]। इस प्रकार, आपकी वर्णित समस्या विभाजन समस्या के लिए अनुकूलन है।