Phân Tách Số Thành 3 Phần Để Tìm Tổng Lớn Nhất

Giới thiệu

Cho một số n, chia n thành ba phần: n/2, n/3, n/4 (lấy phần nguyên). Tiếp tục chia từng phần đó tương tự. Tìm tổng lớn nhất có thể đạt được sau khi chia tối đa 3 lần (hoặc đệ quy vô hạn).

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

Đầu vào: n = 12
Đầu ra: 13. Giải thích: 12 -> 6+4+3=13. Tiếp tục chia 6 -> 3+2+1=6, 4 -> 2+1+1=4, 3 -> 1+1+0=2. Max = 13.

Thuật toán Quy hoạch động

Mảng sums[i] lưu tổng lớn nhất có thể đạt từ số i. Công thức: sums[i] = max(i, sums[i/2] + sums[i/3] + sums[i/4]).

maxBreakSum(n)
Begin
    định nghĩa sums[0..n]
    sums[0] := 0, sums[1] := 1
    for i := 2 to n do
        sums[i] := max(i, sums[i/2] + sums[i/3] + sums[i/4])
    done
    return sums[n]
End

Ví dụ 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 << "Nhập một số: "; cin >> n;
    cout << "Tổng lớn nhất sau khi chia: " << maxBreakSum(n);
    return 0;
}

Kết quả

Nhập một số: 12
Tổng lớn nhất sau khi chia: 13