C++で解く「最も高いビルボード」問題 ― 動的計画法によるアプローチ

ビルボードを設置する際、その高さはできるだけ高くしたいものです。ビルボードは両側に2本の鋼製の支柱で支えられますが、それぞれの支柱は必ず同じ高さでなければなりません。また、溶接によって自由に接合できる棒(ロッド)のコレクションが与えられます。たとえば、長さ1、2、3のロッドがあれば、これらをつなぎ合わせて長さ6の支柱を作ることができます。ここでの課題は、ビルボードを支えられる最大の高さを求めることです。もしビルボードを支えることができない場合は0を返します。

たとえば、入力が [1,2,2,3,3,3,4] の場合、出力は9になります。これは、ロッドを [1,2,2,4](合計9)と [3,3,3](合計9)という2つのグループに分けられるためです。

解法の考え方

この問題は動的計画法(DP)を用いて解きます。ポイントとなるのは、左右の支柱の高さの差に着目することです。

dp[i][j] を「i本目までのロッドを使ったとき、左右の支柱の高さの差が j − 5000 である状態における、低い方の支柱の高さの最大値」と定義します。差は負の値にもなり得るため、オフセットとして5000を加えて配列のインデックスに対応させています。

各ロッドについては、「高い方の支柱に追加する」「低い方の支柱に追加する」「使わない」の3つの選択肢があり、これらをすべて試しながらDPテーブルを更新していきます。

アルゴリズムの手順

• sum := 0、n := ロッドの数、N := 2 * 5000 とします

• (n + 1) × (N + 1) のサイズを持つ2次元配列 dp を -1 で初期化します

• dp[0, 5000] := 0 と設定します(差0・高さ0の初期状態)

• i := 0 から i < n の間、以下を繰り返します

  • j := 0 から j <= N の間、以下を繰り返します

    • x := rods[i] とします

    • j − x >= 0 かつ dp[i, j − x] ≠ -1 の場合:dp[i + 1, j] = max(dp[i + 1, j], dp[i, j − x] + x)(低い方の支柱に追加)

    • j + x <= N かつ dp[i, j + x] ≠ -1 の場合:dp[i + 1, j] = max(dp[i + 1, j], dp[i, j + x])(高い方の支柱に追加)

    • dp[i, j] ≠ -1 の場合:dp[i + 1, j] = max(dp[i, j], dp[i + 1, j])(ロッドを使用しない)

• 最後に dp[n, 5000](差が0、つまり両支柱が等しい高さの状態)を返します

それでは、理解を深めるために以下の実装を見てみましょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int tallestBillboard(vector<int>& rods){
        int sum = 0;
        int n = rods.size();
        int N = 2 * 5000;
        vector<vector<int> > dp(n + 1, vector<int>(N + 1, -1));
        dp[0][5000] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= N; j++) {
                int x = rods[i];
                if (j - x >= 0 && dp[i][j - x] != -1) {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - x] +
                    x);
                }
                if (j + x <= N && dp[i][j + x] != -1) {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + x]);
                }
                if (dp[i][j] != -1) {
                    dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
                }
            }
        }
        return dp[n][5000];
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,2,3,3,3,4};
    cout << (ob.tallestBillboard(v));
}

入力

{1,2,2,3,3,3,4}

出力

9