【C++】1次元オブジェクトとMビンのFirst Fit Decreasing（FFD）アルゴリズムを実装する方法

本記事では、1次元のオブジェクトをM個のビン（容器）に詰める「First Fit Decreasing（ファーストフィット・ディクリーシング）」アルゴリズムをC++で実装するプログラムを紹介します。

First Fit Decreasingとは

First Fit Decreasing（FFD）は、ビンパッキング問題に対する代表的な近似解法の一つです。基本的な流れは次のとおりです。

1. すべてのアイテムをサイズの降順に並べ替える。
2. 各アイテムについて、残り容量が足りている最初のビンへ順番に格納していく。
3. どの既存ビンにも収まらない場合は、新しいビンを用意する。

大きいアイテムから先に詰めることで、小さなアイテムが後から空きスペースへ効率よく収まり、使用するビンの総数を最小限に近づけられるのが特徴です。

必要な関数と擬似コード

このアルゴリズムでは、ビンへの詰め込みを行う関数 binPack() と、バブルソートで降順に並べ替える関数 sort() の2つを用意します。

開始
    関数 binPack() ：必要なビンの数を返す
    binC を 0 で初期化する
    各ビンの残容量 binVal を格納する配列を初期化する
    アイテムを1つずつビンに配置する
    関数 sort() ：バブルソートにより降順に並べ替える
終了

サンプルコード

#include <iostream>
using namespace std;
void binPack(int *a, int s, int n)
{
    int binC = 0;
    int binVal[n];
    for (int i = 0; i < n; i++)
        binVal[i] = s;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            if (binVal[j] - a[i] >= 0)
            {
                binVal[j] -= a[i];
                break;
            }
        }
    for (int i = 0; i < n; i++)
        if (binVal[i] != s)
            binC++;
    cout << "Number of bins required using first fit decreasing algorithm is: " << binC;
}
int* sort(int *seq, int n)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n - 1; j++)
            if (seq[j] < seq[j + 1])
            {
                seq[j] = seq[j] + seq[j + 1];
                seq[j + 1] = seq[j] - seq[j + 1];
                seq[j] = seq[j] - seq[j + 1];
            }
    return seq;
}
int main(int argc, char **argv)
{
    cout << "Enter the number of items in Set: ";
    int n;
    cin >> n;
    cout << "Enter " << n << " items:";
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << "Enter the bin size: ";
    int s;
    cin >> s;
    int *seq = sort(a, n);
    binPack(seq, s, n);
}

コードのポイント

• sort()：隣接する要素を比較・交換するバブルソートで、アイテムを降順に並べ替えます。要素の交換には一時変数を使わず、加減算だけで実現しています。
• binPack()：並べ替えたアイテムを先頭のビンから順に調べ、残容量に収まるビンへ格納していきます。
• 最後に、初期値（ビンサイズ）から値が変化したビンを数えることで、実際に使用されたビンの総数 binC を求めています。

なお、この実装では「すべてのアイテムがビンのサイズ以下である」ことを前提としています。ビンサイズより大きなアイテムは、どのビンにも格納できない点に注意してください。

実行結果

Enter the number of items in Set: 7
Enter 7 items:4
6
7
5
3
2
1
Enter the bin size: 5
Number of bins required using first fit decreasing algorithm is: 3

これは、サイズ4・6・7・5・3・2・1の7つのアイテムを、容量5のビンに詰め込んだ場合の出力例です。アイテムは7・6・5・4・3・2・1の順に降順で処理され、最終的に必要なビンの数は3と判定されます。

※上記のコードでは可変長配列（VLA）を使用しているため、GCCやClangなどではそのままコンパイルできますが、厳密には標準C++の範囲外です。移植性を重視する場合は、std::vector の利用を検討するとよいでしょう。