Chia số thành 3 phần để tìm tổng tối đa

Một số đã cho. Nhiệm vụ của chúng ta là chia số đó thành ba lần cho n / 2, n / 3 và n / 4 và tìm tổng lớn nhất mà chúng ta có thể thực hiện bằng cách chia số thành ba phần.

Ví dụ:50 có thể được chia thành {25, 16, 12}, bây giờ chia từng tập hợp {25, 16, 12}, thành ba bộ phận một lần nữa, v.v. Sau khi hoàn thành phép chia 3 lần, chúng ta sẽ tính tổng để tìm số lớn nhất.

Chương trình này có thể được giải theo cách đệ quy, nhưng trong cách tiếp cận đệ quy, chúng ta cần tìm các kết quả giống nhau cho nhiều lần, vì vậy nếu chúng ta sử dụng cách tiếp cận Lập trình động và lưu trữ dữ liệu đã tính toán trước đó trong một bảng, thì nó sẽ giảm thời gian.

Đầu vào và Đầu ra

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.

Thuật toán

maxBreakSum(n)

Đầu vào: Số đã cho.

Đầu ra: Tổng tối đa sau khi phá vỡ.

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

Ví dụ

#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);
}

Đầu ra

Enter a number: 12
Maximum sum after breaking: 13