বিন প্যাকিং সমস্যা একটি বিশেষ ধরনের কাটিং স্টক সমস্যা। বিন প্যাকিং সমস্যায়, বিভিন্ন ভলিউমের বস্তুগুলিকে অবশ্যই সীমিত সংখ্যক পাত্রে বা বিনে ভলিউম V এর প্রতিটিতে এমনভাবে প্যাক করতে হবে যাতে ব্যবহৃত বিনের সংখ্যা কম হয়। কম্পিউটেশনাল জটিলতা তত্ত্বে, এটি একটি সম্মিলিত NP-হার্ড সমস্যা।
যখন বিনের সংখ্যা 1 এর মধ্যে সীমাবদ্ধ থাকে এবং প্রতিটি আইটেম একটি ভলিউম এবং একটি মান উভয় দ্বারা চিহ্নিত করা হয়, তখন বিনের মধ্যে ফিট করতে পারে এমন আইটেমগুলির মান সর্বাধিক করার সমস্যাটিকে ন্যাপস্যাক সমস্যা হিসাবে পরিচিত।
অ্যালগরিদম
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
