Bin 패킹 알고리즘을 구현하는 C++ 프로그램

빈 포장 문제는 절단 재고 문제의 특수한 유형입니다. 빈 패킹 문제에서 부피가 다른 물체는 사용되는 빈의 수를 최소화하는 방식으로 부피 V의 각각의 한정된 수의 컨테이너 또는 빈으로 패킹되어야 합니다. 계산 복잡도 이론에서는 조합 NP-하드 문제입니다.

bin의 개수를 1개로 제한하고 각 항목이 볼륨과 값으로 특징지어질 때 bin에 들어갈 수 있는 항목의 가치를 최대화하는 문제를 배낭 문제라고 합니다.

알고리즘

Begin
   Binpacking(pointer, size, no of sets)
   Declare bincount, m, i
   Initialize bincount = 1, m=size
   For i = 0 to number of sets
   if (m - *(a + i) > 0) do
      m = m - *(a + i)
      Continue
   Else
      Increase bincount
      m = size;
      Decrement i
      Print number of bins required
End

예시 코드

#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 << "Number of bins required: " << binCount;
}
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 size;
   cin >> size;
   binPacking(a, size, n);
}

출력

Enter the number of items in Set: 3
Enter 3 items:4
6
7
Enter the bin size: 26
Number of bins required: 1