C++で棚の配置問題（Fitting Shelves Problem）を解くプログラムの作成方法

この問題では、壁の長さを表す整数 W、および2種類の棚の長さを表す整数 n と m の3つの値が与えられます。課題は「棚の配置問題（Fitting Shelves Problem）」を解くプログラムを作成することです。

棚を配置した後に壁へ残る空きスペースを最小限に抑える方法を見つける必要があります。さらに副次的な条件として、大きな棚ほど製作コストの面で有利なため、できる限り大きな棚を優先的に使用しなければなりません。

出力は以下の形式で行います。

nサイズの棚の個数　mサイズの棚の個数　残りのスペース

問題の例

入力: W = 12, n = 5, m = 3
出力: 0 4 0

解説

この例では、長さ3の棚をちょうど4つ、壁に収めることができます。

このとき合計の長さは 4 × 3 = 12 となり、

棚の配置後に壁へ余るスペースはゼロになります。

解法のアプローチ

この問題に対するシンプルな解法が、全探索（ブルートフォース）によるアプローチです。壁への棚の配置について考えられるすべての組み合わせを順に調べ、壁に残るスペースを最小化（またはゼロにする）組み合わせを見つけます。

副次的な条件に対応するためには、より長い棚から優先的に配置していくことで、大きな棚を重視します。そして「できるだけ多くの大きな棚を使用しつつ、残りスペースが最小になる組み合わせ」を最適解として採用します。

アルゴリズムの流れ

まず、壁の長さを一方の棚で埋めた場合の残りスペースを初期値とします。その後、もう一方の棚の本数を1本ずつ増やしながら、残りの長さを埋めたときの空きスペースを計算します。空きスペースがそれまでの最小値以下になったタイミングで、そのときの各棚の本数と残りスペースを最適解として記録していきます。この処理をすべての組み合わせに対して繰り返すことで、最も効率の良い配置が求まります。

実装例

以下は、上記の解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;

void solveFittingShelves(int wall, int m, int n){

    int numM = 0, numN = 0, minSpaceLeft = wall;
    int p = wall/m, q = 0, rem = wall%m;
    numM = p;
    numN = q;
    minSpaceLeft = rem;
    while (wall >= n) {
        q += 1;
        wall = wall - n;
        p = wall / m;
        rem = wall % m;
        if (rem <= minSpaceLeft) {
            numM = p;
            numN = q;
            minSpaceLeft = rem;
        }
    }
    cout<<numM<<" "<<numN<<" "<<minSpaceLeft<<endl;
}

int main(){
    int W = 29, m = 3, n = 9;
    cout<<"Length of wall : "<<W<<endl;
    cout<<"Length of shelves : "<<m<<"\t"<<n<<endl;
    cout<<"Optimal Shelves fitting : ";
    solveFittingShelves(W, m, n);
    return 0;
}

出力結果

Length of wall : 29
Length of shelves : 3 9
Optimal Shelves fitting : 0 3 2

このように、壁の長さ29に対して長さ9の棚を3本配置することで、残りスペースをわずか2まで抑える最適な配置が得られました。計算量はO(W/min(n, m))程度であり、壁の長さがそれほど大きくない場合は十分実用的な手法です。