अधिकतम योग ज्ञात करने के लिए संख्या को 3 भागों में तोड़ें

एक नंबर दिया गया है। हमारा काम संख्या को तीन बार n/2, n/3, और n/4 से तोड़ना है और संख्या को तीन भागों में विभाजित करके अधिकतम योग प्राप्त करना है।

उदाहरण के लिए, 50 को {25, 16, 12} में विभाजित किया जा सकता है, अब प्रत्येक सेट {25, 16, 12} को फिर से तीन भागों में विभाजित करें, और इसी तरह आगे भी। भाग को 3 बार तक पूरा करने के बाद, हम योग की गणना करके उनमें से अधिकतम का पता लगाएंगे।

इस कार्यक्रम को पुनरावर्ती तरीके से हल किया जा सकता है, लेकिन पुनरावर्ती दृष्टिकोण में, हमें कई बार एक ही परिणाम खोजने की आवश्यकता होती है, इसलिए यदि हम गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करते हैं और पहले से गणना किए गए डेटा को एक तालिका में संग्रहीत करते हैं, तो यह कम हो जाएगा समय।

इनपुट और आउटपुट

Input:
Let the given number is 12.
Output:
The answer is 13.
At first divide the 12 as (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13.
now divide 6 into three parts (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6.
If we divide the 4 and 3, we can get maximum 4 from them. From all values the maximum is 13.

एल्गोरिदम

maxBreakSum(n)

इनपुट: दी गई संख्या।

आउटपुट: तोड़ने के बाद अधिकतम राशि।

Begin
   define sums array of size n+1
   sums[0] := 0, sums[1] := 1

   for i in range 2 to n, do
      sum[i] := maximum of i and (sums[i/2] + sums[i/3] + sums[i/d])
   done
   return sums[n]
End

उदाहरण

#include<iostream>
#define MAX 1000000
using namespace std;

int max(int a, int b) {
   return (a>b)?a:b;
}

int maxBreakSum(int n) {
   int sumArr[n+1];
   sumArr[0] = 0, sumArr[1] = 1;    //for number 0 and 1, the maximum sum is 0 and 1 respectively

   for (int i=2; i<=n; i++)    //for number 2 to n find the sum list
      sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i);    //divide number by 2, 3, 4
   return sumArr[n];
}

int main() {
   int n;
   cout << "Enter a number: "; cin >> n;
   cout << "Maximum sum after breaking: " << maxBreakSum(n);
}

आउटपुट

Enter a number: 12
Maximum sum after breaking: 13