代数式の最大値を求めるC++プログラム：動的計画法による効率的な実装

この記事では、(x₁ + x₂ + … + xₐ) × (y₁ + y₂ + … + y_b) という形式で表される代数式の最大値を求めるC++プログラムを紹介します。合計 (a + b) 個の整数が与えられたとき、その中から a 個を左辺のグループに、残りの b 個を右辺のグループに割り当てるすべての組み合わせを検討し、それぞれの値を計算することで最大値を導き出します。

全組み合わせを総当たりで調べることも可能ですが、ここでは動的計画法（DP）を活用し、より効率的に解く手法を解説します。

アルゴリズム

開始
    関数 MaxValue() :
    引数:
        a[] = 要素を格納する配列
        x, y = 整数
    関数の処理手順:
    1) 配列要素の合計を求める。
    2) s = 0 として初期化する。
    3) i = 0 から (x + y − 1) までのループを作成し、
       整数を 25 ずつシフトして正の値に変換する。
    4) ブール型配列 p[i][j] を宣言する。
       「i 個の数を選んで和 j を作れる場合に true」を表す。
    5) 配列を初期化する。
    6) i = 0 から (x + y) − 1 までのループで、p[i][j] が true のとき、
       「(x + y) 個の数から i 個を選んで和を j にできる」ことを判定する。
    7) max_value = −INF として初期化する。
    8) i = 0 から (MAX * MAX + 1) − 1 までのループで、
       特定の和が n 個の選択によって到達可能かを確認する。
       if (p[x][i])
           数値を 25 シフトしているため、実際の和へ戻す。
    9) max_value を出力する。
終了

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 25
int MaxValue(int a[], int x, int y) {
    int s = 0;
    for (int i = 0; i < (x + y); i++) {
        s += a[i];
        a[i] += 25;   // 負のインデックスを避けるため25を加算
    }
    bool p[MAX+1][MAX * MAX + 1];
    // 配列を0で初期化
    memset(p, 0, sizeof(p));
    p[0][0] = 1;
    for (int i = 0; i < (x + y); i++) {
        // k は最大でも x（左辺の式には x 個の数が入るため）
        for (int k = min(x, i + 1); k >= 1; k--) {
            for (int j = 0; j < MAX * MAX + 1; j++) {
                if (p[k - 1][j])
                    p[k][j + a[i]] = 1;
            }
        }
    }
    int max_value = -INF;
    for (int i = 0; i < MAX * MAX + 1; i++) {
        if (p[x][i]) {
            int tmp = i - 25 * x;   // シフト分を戻して実際の和を取得
            max_value = max(max_value, tmp * (s - tmp));
        }
    }
    cout << "Maximum Value: " << max_value;
}
int main() {
    int x = 2, y = 2;   // x と y の入力
    int ar[] = { 7, 6, 4, 3 };
    MaxValue(ar, x, y);
    return 0;
}

出力

Maximum Value: 100

コードのポイント解説

このプログラムの核心は動的計画法にあります。配列 p[k][j] は「k 個の数を選んだとき、その和を j にできるかどうか」を記録します。また、数値をあらかじめ 25（MAX）だけシフトしておくことで、入力に負の数が含まれていても配列のインデックスが負になる問題を回避しています。

DPテーブルの構築後、左辺（x 個）の取りうる各和 tmp に対して、右辺の和は「全体の和 s − tmp」となるため、式の値は tmp × (s − tmp) で一意に求められます。これらの候補の中で最大のものが答えとなります。

たとえば x = 2、y = 2、配列 {7, 6, 4, 3} の場合、考えられる組み合わせは次のとおりです。

• (7 + 6) × (4 + 3) = 13 × 7 = 91
• (7 + 4) × (6 + 3) = 11 × 9 = 99
• (7 + 3) × (6 + 4) = 10 × 10 = 100
• (6 + 4) × (7 + 3) = 10 × 10 = 100
• (6 + 3) × (7 + 4) = 9 × 11 = 99
• (4 + 3) × (7 + 6) = 7 × 13 = 91

したがって最大値は 100 となり、プログラムの出力結果と一致することが確認できます。