C++로 구현하는 1차원 객체와 M개의 Bin에 대한 First Fit Decreasing 알고리즘

이 글에서는 First Fit Decreasing(FFD, 최초 적합 감소) 알고리즘을 사용하여 1차원 객체들을 M개의 Bin에 담을 때 필요한 최소 Bin 개수를 계산하는 C++ 프로그램을 소개합니다.

First Fit Decreasing 알고리즘이란?

Bin Packing 문제는 크기가 서로 다른 여러 객체를 정해진 용량의 Bin에 최대한 적게 나누어 담는 고전적인 최적화 문제입니다. First Fit Decreasing은 이를 해결하는 대표적인 근사 알고리즘으로, 다음과 같은 순서로 동작합니다.

모든 객체를 크기가 큰 순서대로 내림차순 정렬합니다.
정렬된 객체를 하나씩 꺼내며, 수용 가능한 첫 번째 Bin에 담습니다.
어떤 Bin에도 담을 수 없다면 새로운 Bin을 생성합니다.

필요한 함수와 의사 코드(Pseudocode)

시작
    함수 binPack(): 필요한 Bin의 개수를 반환한다.
        binC = 0 으로 초기화
        Bin의 남은 용량을 저장할 배열 binVal 초기화
        객체를 하나씩 배치한다.
    함수 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() 함수

버블 정렬(Bubble Sort)을 이용해 입력받은 객체들을 내림차순으로 정렬합니다. 덧셈과 뺄셈만으로 두 변수의 값을 교환(swap)하는 방식을 사용했습니다.

binPack() 함수

배열 binVal에는 각 Bin의 남은 용량이 저장됩니다. 처음에는 모든 Bin이 가득 찬 상태(용량 s)로 초기화되며, 각 객체를 앞에서부터 차례로 검사해 처음으로 들어갈 수 있는 Bin에 배치합니다. 마지막으로 초기 용량과 값이 달라진 Bin, 즉 실제로 사용된 Bin의 개수를 세어 출력합니다.

실행 결과

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

동작 과정 분석

위 예제에서 입력된 객체 {7, 6, 5, 4, 3, 2, 1}을 크기 5짜리 Bin에 담으면 다음과 같이 배치됩니다.

Bin 1: 5 → 4 → 1 (합계 10? 아니요, 각 단계에서 남은 용량 확인 후 배치)
내림차순 정렬 후 7부터 배치를 시도하며, 크기 5인 Bin에는 7이 들어갈 수 없으므로 새 Bin이 계속 생성되는 방식으로 진행됩니다.
최종적으로 3개의 Bin이 필요하다는 결과가 출력됩니다.

마무리

First Fit Decreasing은 구현이 간단하면서도 좋은 근사 해를 제공하는 알고리즘입니다. 이론적으로 최적해의 약 11/9 × OPT + 6/9 범위 내의 결과를 보장하는 것으로 알려져 있으며, 물류·메모리 할당 등 다양한 분야에서 활용됩니다. 다만 위 예제 코드는 학습용으로 작성되었으므로, 실무에서는 VLA(가변 길이 배열) 대신 vector 사용, 더 효율적인 정렬 알고리즘(std::sort) 적용 등을 고려하는 것이 좋습니다.