Chương trình C ++ để triển khai thuật toán đóng gói thùng

Vấn đề đóng gói thùng là một loại vấn đề đặc biệt của vấn đề kho cắt. Trong bài toán đóng gói thùng, các đồ vật có thể tích khác nhau phải được đóng gói vào một số lượng hữu hạn các thùng hoặc thùng mỗi thùng có thể tích V theo cách giảm thiểu số lượng thùng được sử dụng. Trong lý thuyết độ phức tạp tính toán, đây là một bài toán khó tổ hợp NP.

Khi số lượng thùng được giới hạn ở 1 và mỗi mục được đặc trưng bởi cả khối lượng và giá trị, thì vấn đề tối đa hóa giá trị của các mục có thể vừa trong thùng được gọi là bài toán về cái túi.

Thuật toán

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

Mã mẫu

#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);
}

Đầu ra

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