সর্বোচ্চ যোগফল বের করতে সংখ্যাটিকে 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