विभिन्न संप्रदायों के सिक्के एक के बाद एक रखा जाता है, योग

Question

अधिकतम संप्रदायों के सिक्के को एक दूसरे के बाद रखा जाता है। आपको सिक्कों को एक-एक करके चुनना होगा (पहले और आखिरी को छोड़कर) जब तक कि केवल 2 सिक्के (पहले और आखिरी) शेष न हों। प्रत्येक बार जब आप सिक्का चुनते हैं तो आप इसे बाएं और दाएं सिक्के मूल्यों को गुणा करते हैं। समस्या इस तरह के क्रम में सिक्कों को चुनना है ताकि सभी गुणाओं का योग अधिकतम हो।

माना कि सिक्के रखा जाता है 1, 6, 7, के रूप में 4

सिक्के लेने के लिए 2 तरीके हैं::

सबसे पहले जिस तरह से: पहले 6 लेने, यह 1 में परिणाम होगा उदाहरण के लिए * 7 = 7 और उसके बाद 7 लेने, इस परिणाम होगा में 1 * 4 = 4, इसलिए कुल 7 + 4 =

दूसरा तरीका होगा: पहले 7 लेने, इस 6 * 4 में परिणाम होगा = 24 और फिर 6 चुनें, इसका परिणाम 1 * 4 = 4 होगा, इसलिए कुल 2 होगा 4 + 4 =

जैसा कि 28 सबसे बड़ा है, यह हमारा जवाब है।

मुझे सभी संभावित मामलों के माध्यम से पुनरावर्ती रूप से ट्रैवर्सिंग और उनके आउटपुट मूल्यों की तुलना करके सही उत्तर मिल सकता है लेकिन यह समाधान घातीय समय के रूप में बहुत अक्षम है। कृपया बताएं कि इस समस्या को और अधिक कुशलता से कैसे हल किया जा सकता है।

संपादित करें: पुनरावर्ती समाधान

int remove (int a [], int end, int pos) { 
    int tmp = a[pos]; 
    for (int i = pos + 1; i <= end; i++) { 
     a[i - 1] = a[i]; 
    } a[end] = 0; 
    return tmp; 
} 

int * insert (int a [], int end, int pos, int val) { 
    for (int i = end; i >= pos; i--) { 
     a[i + 1] = a[i]; 
    } a[pos] = val; 
    return a; 
} 

/* a: input array, {1, 7, 6, 4} 
    end: array last index, 3 for above case 
*/ 
int getMaxSum (int a [], int end, int sum = 0) { 
    if (end == 1) { 
     return sum; 
    } 

    int maxSum = 0; 

    for (int i = 1; i < end; i++) { 
     auto mult = a[i - 1]*a[i + 1]; 
     auto val = remove(a, end, i); 
     auto tmp = getMaxSum (a, end - 1, sum + mult); 
     if (tmp > maxSum) 
      maxSum = tmp; 
     insert(a, end - 1, i, val); 
    } 

    return maxSum; 
} 

Answer 1

यह संशोधित Matrix Chain Multiplication समस्या का उपयोग कर Dynamic programming का उपयोग कर हल किया जा सकता। आयामों की

• मैट्रिक्स एम 1 axb आयामों की
• मैट्रिक्स M2 BXC
• :

  मान लीजिए दी गई संख्याओं ए, बी, सी, डी

  A B C D 
  1 6 7 4 
  

  अब इन संख्या में कन्वर्ट कर रहे हैं

  आयामों के मैट्रिक्स एम 3 सीएक्सडी

  M1 M2 M3 
  AB BC CD 
  16 67 74 
  

आम तौर पर, यदि आयाम एबी और बीसी के 2 संगत मैट्रिक्स गुणा किए जाते हैं तो गुणा की लागत AB x BC = ABC है। ABC is product of 3 elements A, B & C।

इस संशोधित एल्गोरिदम में, लागत एएक्ससी होगी (चूंकि तत्व [i] चुनने के परिणामस्वरूप [i-1]x[i+1] खर्च होंगे)।

वह है, AB x BC = AC। AC is product of 2 elements A & C।

अब, मैट्रिस एम 1, एम 2 और एम 3 को सभी संभावित तरीकों से संश्लेषित करने का प्रयास करें, जैसे लागत अधिकतम है।

संभव कोष्ठकों:

[1] (M1 (M2 M3)) 
[2] ((M1 M2) M3) 


[1] 
{AB x (BCxCD)} => {AB x BD} 
{(AB) x (6 x 4 = 24)} => {1 x 4 = 4} , so 24 + 4 = 28 
Elements picking order {C} -> {B} 

[2] 
{(AB x BC) x CD} => {AC x CD} 
{(1 x 7 = 7) x CD} => {1 x 4 = 4} , so 7 + 4 = 11 
Elements picking order {B} -> {C} 

तो, [1] का उपयोग कर, मूल्य अधिकतम है, यानी 28 है, और तत्वों निम्न क्रम में उठाया जाना चाहिए: C -> B।

Answer 2

मैं आपके फ़ंक्शन getMaxSum के लिए कैश के उपयोग का सुझाव दूंगा। दरअसल, यह एल्गोरिदम की घातीय जटिलता से बच नहीं पाता है, लेकिन यह दोहराने योग्य गणनाओं को व्यवस्थित करने में काफी समय बचाता है। यहाँ पायथन में मेरी कार्यान्वयन है (क्योंकि यह लग रहा है काफी प्रकार):

cache = {} 

def getMaxSum(a): 
    if tuple(a) in cache: 
     return cache[tuple(a)] 

    sum_arr = [] 
    for i in range(1, len(a) - 1): 
     s = a[i-1] * a[i+1] + getMaxSum(a[:i] + a[i+1:]) 
     sum_arr.append(s) 

    cache[tuple(a)] = max(sum_arr) if sum_arr else 0 

    return cache[tuple(a)] 

print(getMaxSum([1, 6, 7, 4])) # 28 
print(getMaxSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])) # 3420 

यह 20.

एक गैर घातीय समाधान के लिए के रूप में करने के लिए लंबाई के साथ सूची के लिए काफी तेजी से काम करता है, मुझे लगता है कि, यह एक है कठिन गणितीय प्रश्न के उत्तर देने के लिए एक गंभीर शोध की आवश्यकता है।

Answer 3

यहां एक गतिशील प्रोग्रामिंग सी ++ समाधान है जो मुझे लगता है कि एट्रान द्वारा दिए गए मैट्रिक्स चेन गुणात्मक विचार के काफी करीब है। हम sums[i][j] तालिका में स्टोर करते हैं जो अधिकतम 0 सूचकांक i से शुरू होता है और सूचकांक j में समाप्त होता है। हम तीन सिक्कों (j-i = 2) के अनुक्रमों से शुरू होने वाले सूचकांक के बीच सिक्कों की संख्या को फिर से शुरू करते हैं। पुनरावृत्ति चरण sums[i][j]sum[i][k] + sum[k][j] + coins[i]*coins[j] में से सबसे बड़ा चुनना है। यदि j-i<2, m[i][j]=0।

int maxSum(const std::vector<int>& coins){ 
    int n = coins.size(); 
    std::vector<std::vector<int>> sums; 
    for (int i = 0; i < n-1; ++i){ 
    sums.push_back(std::vector<int>(n)); 
    } 
    for (int l = 2; l < n; ++l){ 
    for (int i = 0; i < n - l; ++i){ 
     int j = i + l; 
     sums[i][j] = -1; 
     for (int k = i+1; k < j; k++){ 
     int val = sums[i][k] + sums[k][j] + coins[i]*coins[j]; 
     if (val > sums[i][j]){ 
      sums[i][j] = val; 
     } 
     } 
    } 
    } 
    return sums[0][n-1]; 
} 

आसानी से समय जटिलता देखा जा सकता है है हे (एन^3) और अंतरिक्ष O(N^2) है।

Answer 4

मैं इसे (मुझे लगता है) डीपी के साथ हल करने में कामयाब रहा। हालांकि, इसकी स्पेस आवश्यकता 2^n का एक कारक है जहां n हटाए जाने वाले सिक्के की संख्या है।

मूल विचार यह है कि हम एन-आयामी अंतरिक्ष में बिंदुओं के बीच ट्रैवर्स कर रहे हैं।

कहते हैं: coins = [ _, x, x, x, _ ]

3 "मध्यम" सिक्के हैं। यदि हम 1 एस (और 0 एस) द्वारा सिक्कों की उपस्थिति (और अनुपस्थिति) को इंगित करते हैं, तो हम (1, 1, 1) से (0, 0, 0) पर जा रहे हैं।

बीच में, कई संक्रमणकालीन राज्य हैं जिन्हें हम कई पथों तक पहुंच सकते हैं।

उदाहरण के लिए: ->(1, 1, 0) ->(1, 0, 0) या (1, 1, 1) ->(1, 0, 1) ->(1, 0, 0)(1, 0, 0)(1, 1, 1) के रूप में पहुँचा जा सकता है।

इसलिए, यदि आसन्न संख्याओं का गुणा स्कोर है, तो हम राज्य (1, 0, 0) पर जा सकते हैं ताकि इसे आगे बढ़ने वाले पथों का उच्चतम स्थान प्राप्त किया जा सके। चूंकि प्रत्येक संक्रमण को 1 से 0 को बदलकर "कदम उठाने" की आवश्यकता होती है, इसलिए हम (1, 1, 1) से (0, 0, 0) पर राज्यों के मूल्य को सहेज सकते हैं। अंतिम उत्तर (0, 0, 0) पर संग्रहीत किया जाएगा।

नीचे ऐसा एक कार्यान्वयन है। मुझे यकीन नहीं था कि एन-आयामी राज्यों का प्रतिनिधित्व करने के बारे में कैसे जाना है।इसलिए, मैंने अभी एक पूर्णांक का उपयोग किया है जो 2^n - 1 से घटता है और फिर राज्य को एन्कोड करने के लिए इसके बाइनरी मान का उपयोग करता है। तो, यदि cur_state = 6 (110), तो इसका मतलब है कि हमने तीसरा "मध्य" सिक्का हटा दिया है।

संक्रमण करने के लिए, हम cur_state से घटाते हैं।

(चेतावनी: सिक्का के आसन्न सिक्कों को हटाने के लिए कुछ बदसूरत सूचकांक गणना का उपयोग किया गया था)।

coins = [1, 6, 7, 4] 
middle_length = len(coins) - 2 
upper_limit = 2**middle_length 

values = [0] * upper_limit 

for cur_state in range(upper_limit - 1, 0, -1): 
    binary = bin(cur_state)[2:].zfill(middle_length) 
    for k, a in enumerate(binary): 
     if a == '1': 
      next_state = cur_state - 2**(middle_length - k - 1) 
      left_coin = k - (binary[:k][::-1] + '1').find('1') 
      right_coin = (binary[k + 1:] + '1').find('1') + k + 2 
      transit_value = (coins[left_coin] * coins[right_coin]) 
      if values[cur_state] + transit_value > values[next_state]: 
       values[next_state] = values[cur_state] + transit_value 

print(values[0]) 

Answer 5

यह दिखाने के लिए कि अनुक्रमित i और j के बीच सबसे अच्छा उन्मूलन आदेश की समस्या दो subproblems f(i,k) और f(k,j) में f(i,j) का सबसे अच्छा विभाजन करने के लिए कम किया जा सकता आसान है। चूंकि अंततः a[i] को a[k] द्वारा गुणा किया जाना चाहिए जब मध्य तत्वों को समाप्त कर दिया गया है (या a[k]a[i] के समीप है), हम i,k,j को ठीक कर सकते हैं और फ़ंक्शन को प्रत्येक उपप्रोबम पर पुन: लागू कर सकते हैं। बेस केस नीचे जावास्क्रिप्ट कोड में उल्लिखित हैं। यह समाधान अनिवार्य रूप से एरी हिटानेन के समान है।

function f(a,i,j){ 
    if (Math.abs(i - j) === 2) 
    return a[i] * a[j]; 

    if (Math.abs(i - j) === 1) 
    return 0; 

    var best = -Infinity; 

    for (var k=i+1; k<j;k++){ 
    best = Math.max(best, a[i] * a[j] + f(a,i,k) + f(a,k,j)); 
    } 

    return best; 
} 

var a = [1,6,7,4]; 

console.log(f(a,0,3)); // 28