C++で代数式の最小値を求めるプログラム（動的計画法による効率的な解法）

この記事では、(x1 + x2 + x3 + … + xa) × (y1 + y2 + … + yb) という形式の代数式の最小値を求めるC++プログラムを紹介します。

合計 (a + b) 個の整数が与えられたとき、「a 個の数で左辺を構成し、残りの b 個の数で右辺を構成する」すべての組み合わせを考え、それぞれの値を計算することで最小値を導き出せます。しかし、全組み合わせを素朴に試すと計算量が膨大になってしまうため、本プログラムでは動的計画法（DP）を用いて効率的に解きます。

アルゴリズム

処理の流れは以下の擬似コードの通りです。

Begin
    function MinValue() :
    引数:
    a[] = 要素を格納する配列
    x, y = 整数
    処理内容:
    1) 配列要素の総和を求める。
    2) s = 0 として初期化する。
    3) i = 0 ～ (x + y) - 1 のループで、各要素に25を加えて正の値へシフトする。
    4) ブール型2次元配列 p[i][j] を宣言する。「i 個の数を選んで合計 j が作れるとき true」を表す。
    5) 配列を初期化する。
    6) i = 0 ～ (x + y) - 1 のループで DP を更新する。p[i][j] が true なら、(x + y) 個の中から i 個を選んで合計 j にできることを意味する。
    7) min_value = INF で初期化する。
    8) 「x 個の数を選んで作れる合計」を順に調べ、式の値を計算して最小値を更新する（シフト分の25を差し引いて本来の合計に戻す）。
    9) min_value を出力する。
End

アルゴリズムのポイント

・25のシフト：入力には負の数も含まれる可能性があるため、各要素にあらかじめ25を加算します。これによりDPテーブルの添字が負になるのを防ぎます。最終的に答えを求める際は、選んだ x 個に対応して 25 × x を差し引けば本来の合計値を復元できます。

・式の変形：全体の総和を s、左辺に選んだ x 個の合計を tmp とすると、右辺の合計は (s − tmp) になります。したがって式の値は「tmp × (s − tmp)」と表せます。到達可能な tmp をすべて列挙し、その中で最小の値を採用すればよいのです。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 25

int MinValue(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++) {
        // 左辺の式は x 個の数しか持たないため、k は最大 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 min_value = INF;
    for (int i = 0; i < MAX * MAX + 1; i++) {
        if (p[x][i]) {
            int tmp = i - 25 * x; // シフト分を戻して本来の合計を得る
            min_value = min(min_value, tmp * (s - tmp));
        }
    }
    cout << "Minimum Value: " << min_value;
}

int main() {
    int x = 2, y = 2; // x と y を入力
    int ar[] = { 7, 6, 4, 3 };
    MinValue(ar, x, y);
    return 0;
}

実行結果

Minimum Value: 91

実行結果の解説

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

よって最小値は 91 となり、プログラムの出力と一致します。このようにDPを活用することで、全組み合わせを列挙することなく効率的に最小値を求められます。