संख्या को 3 भागों में तोड़कर अधिकतम योग ढूंढना

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

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

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

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

इनपुट: दी गई संख्या 12 है।
आउटपुट: उत्तर 13 है।
पहले 12 को विभाजित करें (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13।
अब 6 को तीन भागों में विभाजित करें (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6।
यदि हम 4 और 3 को विभाजित करते हैं, तो हम उनसे अधिकतम 4 प्राप्त कर सकते हैं।
सभी मानों से अधिकतम 13 है।

एल्गोरिदम

maxBreakSum(n)

इनपुट: दी गई संख्या
आउटपुट: तोड़ने के बाद अधिकतम योग

शुरुआत
    sums ऐरे को आकार n+1 का परिभाषित करें
    sums[0] := 0, sums[1] := 1
    i रेंज 2 से n में, करें
        sum[i] := i और (sums[i/2] + sums[i/3] + sums[i/4]) का अधिकतम
    पूर्ण
    वापस sums[n]
अंत

उदाहरण (C++ कोड)

#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 (int i = 2; i <= n; i++)
        sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i);
    
    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