แบ่งตัวเลขออกเป็น 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