C++로 구현하는 빈 패킹(Bin Packing) 알고리즘 완벽 가이드

빈 패킹(Bin Packing) 문제는 절단 재고(Cutting Stock) 문제의 특수한 형태입니다. 이 문제는 서로 다른 부피를 가진 물체들을 각각 용량 V를 가진 유한 개의 컨테이너(빈)에 담을 때, 사용되는 빈의 개수를 최소화하는 방법을 찾는 것이 목표입니다. 계산 복잡도 이론에서 빈 패킹은 조합론적 NP-난해(NP-hard) 문제로 분류됩니다.

흥미로운 관련 문제로, 빈의 개수가 1개로 제한되고 각 물건이 부피와 가치를 모두 가질 때, 빈에 담을 수 있는 물건들의 가치 합을 최대화하는 문제를 배낭(Knapsack) 문제라고 합니다.

알고리즘 동작 원리

이 구현에서는 입력된 순서대로 물건을 차례로 검사하며 현재 빈에 남은 용량이 충분하면 담고, 그렇지 않으면 새로운 빈을 여는 그리디(Greedy) 방식을 사용합니다.

시작
    Binpacking(포인터, 크기, 집합의 개수)
    bincount, m, i 선언
    bincount = 1, m = size 로 초기화
    i = 0 부터 집합의 개수까지 반복
    if (m - *(a + i) > 0) 이면
        m = m - *(a + i)
        계속 진행
    아니면
        bincount 증가
        m = size
        i 감소
    필요한 빈의 개수 출력
종료

C++ 예제 코드

다음 코드는 위 알고리즘을 C++로 구현한 것입니다. 포인터 연산을 활용해 배열 요소에 접근하며, 현재 빈의 남은 용량(m)과 각 물건의 크기를 비교하여 처리합니다.

#include<iostream>
using namespace std;

void binPacking(int *a, int size, int n) {
    int binCount = 1;   // 필요한 빈의 개수
    int m = size;       // 현재 빈의 남은 용량
    for (int i = 0; i < n; i++) {
        if (m - *(a + i) > 0) {
            // 현재 빈에 물건을 담을 수 있는 경우
            m -= *(a + i);
            continue;
        } else {
            // 새로운 빈이 필요한 경우
            binCount++;
            m = size;
            i--;  // 같은 물건을 새 빈에 다시 시도
        }
    }
    cout << "필요한 빈의 개수: " << binCount;
}

int main(int argc, char **argv) {
    cout << "집합에 들어갈 물건의 개수를 입력하세요: ";
    int n;
    cin >> n;
    cout << n << "개의 물건을 입력하세요:";
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << "빈의 크기를 입력하세요: ";
    int size;
    cin >> size;
    binPacking(a, size, n);
}

실행 결과

물건 3개(4, 6, 7)를 크기 26인 빈에 담는 예제입니다. 모든 물건의 합이 17로 빈의 용량보다 작기 때문에 빈 하나로 충분합니다.

집합에 들어갈 물건의 개수를 입력하세요: 3
3개의 물건을 입력하세요:4
6
7
빈의 크기를 입력하세요: 26
필요한 빈의 개수: 1

참고 사항

이 구현은 입력 순서대로 물건을 배치하는 단순한 그리디 방식으로, 최적해를 보장하지는 않습니다. 실제 환경에서는 First Fit Decreasing(FFD), Best Fit 등 더 정교한 휴리스틱 기법을 함께 고려하는 것이 좋습니다. 또한 가변 길이 배열(VLA)은 표준 C++이 아니므로, 실무에서는 std::vector<int> 사용을 권장합니다.