C++でボードを正方形に分割する最小コストの求め方

概念

長さ p、幅 q のボードが与えられたとき、このボードを p×q 個の正方形に分割する際のコストを最小にすることを目指します。ボードの各辺にはそれぞれ切断コストが設定されており、コストが最小になるような切断の順序を選択することが求められます。

例

下図のようなボードを正方形に分割する場合、最適な切断方法は以下の通りです。

このケースにおける合計最小コストは 65 となり、以下の手順で計算されます。

初期値 : Total_cost = 0
Total_cost = Total_cost + 辺のコスト × 現在のピース数
コスト5 水平切断 : Cost = 0 + 5*1 = 5
コスト5 垂直切断 : Cost = 5 + 5*2 = 15
コスト4 垂直切断 : Cost = 15 + 4*2 = 23
コスト3 水平切断 : Cost = 23 + 3*3 = 32
コスト3 垂直切断 : Cost = 32 + 3*3 = 41
コスト2 水平切断 : Cost = 41 + 2*4 = 49
コスト2 垂直切断 : Cost = 49 + 2*4 = 57
コスト2 垂直切断 : Cost = 57 + 2*4 = 65

解法のアプローチ

この種の問題は貪欲法（グリーディ法）を用いて解くことができます。総コストを S とすると、S = b1x1 + b2x2 … + bkxk と表せます。ここで、xi はある辺の切断コスト、bi は対応する係数であり、bi は切断プロセス終了時までにその辺 xi に対して行った切断の総回数で決まります。

重要なのは、係数の合計は常に一定であるという点です。したがって、S を最小にするような bi の分布を求める必要があります。これを実現するには、コストの大きい辺からできるだけ早く切断することで最適な S に到達できます。同じコストを持つ複数の辺が存在する場合は、どの辺から先に切断しても結果には影響しません。

C++プログラム

以下は上記のアプローチを実装した解法です。まず辺の切断コストを降順にソートし、次にコストの高いものから低いものへとループ処理しながら解を構築していきます。各辺を選択するたびに、対応する方向（垂直または水平）のピース数カウントを 1 ずつ増やし、そのカウントを対応する辺の切断コストと掛け合わせて総コストに加算します。

サンプルコード

// C++ program to divide a board into p*q squares
#include <bits/stdc++.h>
using namespace std;
int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
    int res1 = 0;
    sort(X1, X1 + p, greater<int>());
    sort(Y1, Y1 + q, greater<int>());
    int hzntl = 1, vert = 1;
    int i = 0, j = 0;
    while (i < p && j < q){
        if (X1[i] > Y1[j]){
            res1 += X1[i] * vert;
            hzntl++;
            i++;
        }
        else{
            res1 += Y1[j] * hzntl;
            vert++;
            j++;
        }
    }
    int total = 0;
    while (i < p)
        total += X1[i++];
    res1 += total * vert;
    total = 0;
    while (j < q)
        total += Y1[j++];
    res1 += total * hzntl;
    return res1;
}
int main(){
    int p = 6, q = 4;
    int X1[p-1] = {3, 2, 4, 2, 5};
    int Y1[q-1] = {5, 2, 3};
    cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
    return 0;
}

出力

65