সংখ্যাকে ৩ ভাগে ভাগ করে সর্বোচ্চ যোগফল বের করা

একটি সংখ্যা দেওয়া আছে। আমাদের কাজ হল সংখ্যাকে n/2, n/3, এবং n/4 দ্বারা তিনবার ভাগ করে সর্বোচ্চ যোগফল বের করা যা তিনটি ভাগফলের যোগফল থেকে পাওয়া যাবে।

উদাহরণস্বরূপ, ৫০ কে {25, 16, 12}-এ ভাগ করা যায়। এখন সেট {25, 16, 12}-এর প্রতিটি উপাদানকে আবার তিন ভাগে ভাগ করুন, এবং так дале। ভাগ প্রক্রিয়া ৩ বার সম্পন্ন হলে যোগফল বের করে সর্বোচ্চ মানটি খুঁজে বের করুন।

এই প্রোগ্রাম রিকার্সিভভাবে সমাধান করা যায়, কিন্তু রিকার্সিভ পদ্ধতিতে একই ফলাফল বারবার বের করতে হয়। তাই ডাইনামিক প্রোগ্রামিং পদ্ধতি এবং পূর্বে গণনা করা ডেটা টেবিলে সংরক্ষণ করলে সময় কমবে।

ইনপুট এবং আউটপুট

ইনপুট: দেওয়া সংখ্যা ১২।
আউটপুট: উত্তর ১৩।
প্রথমে ১২ কে ভাগ করলে (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13।
এখন ৬ কে তিন ভাগে ভাগ করলে (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6।
৪ এবং ৩ কে ভাগ করলে সর্বোচ্চ ৪ পাওয়া যায়।
সকল মানের মধ্যে সর্বোচ্চ ১৩।

অ্যালগরিদম

maxBreakSum(n)

ইনপুট: দেওয়া সংখ্যা।
আউটপুট: ভাগ করার পর সর্বোচ্চ যোগফল।

শুরু
  n+1 আকারের sums অ্যারে সংজ্ঞায়িত করুন
  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