Excel VBAでレシピ配置を最適化する方法｜多重ナップサック問題として考えるアルゴリズム設計

Excelにある複数のレシピデータを、決められたページ数や配置枠の中に効率よく収めたい場合、単純な並び替えだけでは解決が難しいことがあります。特に「1ページあたり横4列」「各列の高さは30行まで」「できるだけ少ないページ数にしたい」といった条件がある場合は、組み合わせ最適化問題として考える必要があります。

この記事では、このようなレシピ配置の問題を多重ナップサック問題として整理し、VBAで実装する際の考え方や、現実的な解法となるアルゴリズム設計について解説します。

レシピ配置問題を多重ナップサック問題として整理する

今回のような問題では、レシピ1件ごとの行数が「荷物の重さ」、1つの配置枠が「ナップサックの容量」と考えることができます。

例えば、1つの列に30行まで配置できる場合、各レシピには以下のような情報があります。

ただし通常のナップサック問題と異なる点は、ナップサックの数が最初から決まっていないことです。そのため、先に箱の数を決めるのではなく、必要な箱数を探索する問題として考える方が自然です。

ナップサックの数は総行数だけでは正確に決められない

レシピ全体の行数を合計して30で割れば、おおよその必要数は求められます。しかし、この値は理論上の最低数であり、実際の配置数とは一致しない場合があります。

例えば、以下のような3つのレシピがあるとします。

• レシピA：18行
• レシピB：18行
• レシピC：14行

合計50行なので、30行の枠なら2つ必要に見えます。しかし、18行と18行は同じ枠に入らないため、実際には3枠必要になります。

このように、単純な割り算ではなく、各レシピの組み合わせによって必要ページ数が変化します。

実用的には貪欲法から始めるのがおすすめ

最適解を完全に求める方法としては、全組み合わせを調べる方法があります。しかし、レシピ数が増えると組み合わせ数が爆発的に増えるため、Excel VBAで扱うには現実的ではありません。

そこで実務では、まず貪欲法（グリーディ法）を利用する方法が一般的です。これは「その時点で最も良さそうな選択を繰り返す」という考え方です。

例えば以下のような流れになります。

1. レシピを行数の大きい順に並べる
2. 現在空いている配置枠の中で入る場所を探す
3. 入らなければ新しい枠を作る
4. すべて配置できるまで繰り返す

この方法は必ず最適解になるわけではありませんが、多くの実務データでは高速に十分良い結果を得られます。

VBAで実装する場合の基本的な処理手順

Excel VBAで作成する場合は、レシピ情報を配列やコレクションとして管理し、配置枠ごとの残り容量を記録すると扱いやすくなります。

例えば、各ページの各列を以下のような配列で管理できます。

ページ1 列1 残り行数 12
ページ1 列2 残り行数 5
ページ1 列3 残り行数 30

新しいレシピを配置するときは、残り行数が十分ある列を検索し、配置後に残り容量を減らします。

疑似的な処理イメージは以下になります。

レシピを行数順に並べる
For Each レシピ
    配置可能な列を検索
    If 見つかった場合 Then
        その列へ配置
    Else
        新しい列を追加
    End If
Next

より良い結果を求める場合の改善方法

貪欲法だけでは配置の無駄が発生する場合があります。その場合は、配置後に入れ替え処理を追加すると改善できます。

例えば、最後に余った5行のスペースと、別ページにある20行のレシピを交換することで、ページ数を減らせる可能性があります。

このような改善方法には以下のようなアルゴリズムがあります。

• 局所探索法
• 焼きなまし法
• 遺伝的アルゴリズム
• 動的計画法

ただし、Excel VBAで大量データを処理する場合は、まず貪欲法を実装し、必要に応じて改善する流れがおすすめです。

4列配置を考慮する場合のポイント

今回のように横4列で配置する場合、1ページを1つのナップサックとして考えるより、ページ内に4つの容量30のナップサックが存在すると考えると整理しやすくなります。

つまり、目的は「必要なページ数を最小化すること」であり、そのためにはページ内の4列をできるだけ無駄なく埋める必要があります。

例えば、ページごとの使用量を以下のように評価すると、より良い配置を探せます。

各列の空きを小さくするほど、必要ページ数を減らせる可能性が高まります。

まとめ｜ページ数を最小化するには箱数を決めずに配置を試す

レシピ一覧をページ内に効率よく配置する問題では、最初にナップサック数を決めるのではなく、配置しながら必要数を求める考え方が適しています。

Excel VBAで実装する場合は、まず行数順に並べたレシピを貪欲法で配置し、その後必要に応じて入れ替え処理などで改善する方法が現実的です。

完全な最適解を求めることはデータ量によって難しくなりますが、実務では「短時間で十分良い結果を出すアルゴリズム」を選択することが重要になります。