C++ প্রোগ্রাম: বিন প্যাকিং অ্যালগরিদম বাস্তবায়ন

বিন প্যাকিং সমস্যা একটি স্পেশাল টাইপের কাটিং স্টক প্রব্লেম। বিন প্যাকিং সমস্যাতেও, বিভিন্ন ভলিউমের অবজেক্টগুলোকে একটি ফাইনাইট সংখ্যক কন্টেইনার বা বিনে প্যাক করতে হয় যারা প্রতিটির ভলিউম V, এমনভাবে যাতে ব্যবহার করা বিনের সংখ্যা মিনিমাম হয়। কম্পিউটেশনাল কমপ্লেক্সিটি থিওরিতে, এটি একটি কম্বিনেশনাল NP-hard প্রব্লেম।

যখন বিনের সংখ্যা ১-এ সীমাবদ্ধ থাকে এবং প্রতিটি আইটেম ভলিউম এবং ভ্যালু দুটো দিয়ে ক্যারেক্টারাইজড থাকে, তবে বিনে ফিট হয়ে যেতে পারা আইটেমের ভ্যালু ম্যাক্সিমাইজ করার সমস্যাকে ন্যাপস্যাক প্রব্লেম বলা হয়।

অ্যালগরিদম

শুরু
  Binpacking(pointer, size, no of sets)
  bincount, m, i ডিক্লেয়ার করুন
  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
শেষ

উদাহরণ কোড

#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