数値を3つの部分に分割して最大合計を求めるアルゴリズム（動的計画法）

ある数値が与えられたとき、その数を n/2、n/3、n/4 に相当する3つの部分に分割し、得られる合計の最大値を求めるのがこの問題の目的です。

問題の概要

例として、50 は {25, 16, 12} に分割できます。次に、{25, 16, 12} の各値をさらに3つに分割し、これを繰り返します。すべての分割が完了した後、合計を計算してその最大値を求めます。

ただし、分割するとかえって合計が減ってしまう場合もあります。たとえば 5 を (5/2 + 5/3 + 5/4) = 2 + 1 + 1 = 4 と分割すると、元の値より小さくなります。そこで、「分割する」と「そのまま使う」のどちらか大きい方を選択することがポイントになります。

この問題は再帰的にも解けますが、その場合は同じ結果を何度も計算することになり非効率です。動的計画法（DP）を使って一度計算した結果をテーブルに保存しておけば、計算時間を大幅に短縮できます。

入力と出力

Input:
与えられた数値は 12
Output:
答えは 13
まず 12 を (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13 と分割します。
次に 6 を3つに分割すると (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6 となり、元の 6 より小さくなります。
同様に 4 と 3 を分割しても、そこから得られる最大値はそれぞれ 4 と 3 のままです。
すべての値の中で最大なのは 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
        sums[i] := maximum of i and (sums[i/2] + sums[i/3] + sums[i/4])
    done
    return sums[n]
End

各 i について「i をそのまま使った場合の値」と「i/2 + i/3 + i/4 に分割した場合の合計」を比較し、大きい方を記録していきます。0 と 1 については、分割しても意味がないため、それぞれ 0 と 1 がそのまま最大値になります。

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;     //数値0と1に対する最大値はそれぞれ0と1

    for (int i=2; i<=n; i++)     //2からnまでの各数値について最大合計を求める
        sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i);     //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

計算量

このアルゴリズムは 2 から n までを一度だけ走査するため、時間計算量は O(n) です。また、途中結果を保存する配列が必要となるため、空間計算量も O(n) となります。再帰だけで解いた場合と比べ、重複する計算がなくなるため大幅に高速化できるのが大きな利点です。