সমস্যা বিবরণ
m সংখ্যক ভিন্ন ওজন 가진 এলিমেন্ট এবং ধারিতব্যতা C 가진 বিনগুলো দেওয়া আছে। প্রতিটি এলিমেন্টকে একটি বিনে অ্যাসাইন করতে হবে যাতে ব্যবহৃত বিনের সংখ্যা ন্যূনতম হয়। ধরে নেওয়া হয় সব এলিমেন্টের ওজন বিনের ধারিতব্যতার চেয়ে কম।
অ্যাপ্লিকেশন
- মাল্টিপল ডিসকে ডেটা রাখা।
- ট্রাকের মতো কন্টেইনার লোড করা।
- রেডিও/টিভি ব্রেকে বিজ্ঞাপন প্যাকিং।
- জব শিডিউলিং।
উদাহরণ
Input: weight[] = {4, 1, 8, 1, 4, 2} Bin Capacity c = 10
Output: 2
কমপক্ষে ২টি বিন লাগবে। প্রথম বিন: {4, 4, 2}, দ্বিতীয় বিন: {8, 2}
লোয়ার বাউন্ড
সর্বোচ্চ বিনের ন্যূনতম সংখ্যা = ceil(Total Weight / Bin Capacity)। উপরের উদাহরণে ceil(20/10) = 2।
অনলাইন অ্যালগরিদম
এলিমেন্টগুলো একটা একটা আসে (অজানা অর্ডারে), প্রতিটিকে বিনে রাখতে হয় আগামি এলিমেন্ট বিবেচনা করার আগে।
Next Fit
নেক্সট এলিমেন্ট প্রসেস করার সময় চেক করা হয় সেটি শেষ এলিমেন্টের বিনে ফিট হয় কিনা। না হলে নতুন বিন খোলা হয়।
C++ ইমপ্লিমেন্টেশন
// C++ program to calculate number of bins required using next fit algorithm.
#include <bits/stdc++.h>
using namespace std;
int nextFit(int weight1[], int m, int C) {
int res = 0, bin_rem = C;
for (int i = 0; i < m; i++) {
if (weight1[i] > bin_rem) {
res++;
bin_rem = C - weight1[i];
} else
bin_rem -= weight1[i];
}
return res;
}
int main() {
int weight1[] = {3, 6, 5, 8, 2, 4, 9};
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout << "Number of bins required in Next Fit : " << nextFit(weight1, m, C);
return 0;
}
আউটপুট
Number of bins required in Next Fit : 4
Next Fit সিম্পল অ্যালগরিদম। O(m) টাইম এবং O(1) এক্সট্রা স্পেস।
First Fit
পূর্বের বিনগুলো স্ক্যান করে প্রথম ফিট হয়ে যাওয়া বিনে এলিমেন্ট রাখা হয়। কোনো বিনে না ফিট হলে নতুন বিন।
C++ ইমপ্লিমেন্টেশন
// C++ program to find number of bins needed using First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
int firstFit(int weight1[], int m, int C) {
int res = 0;
int bin_rem[m];
for (int i = 0; i < m; i++) {
int j;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight1[i]) {
bin_rem[j] -= weight1[i];
break;
}
}
if (j == res) {
bin_rem[res] = C - weight1[i];
res++;
}
}
return res;
}
int main() {
int weight1[] = {2, 5, 4, 7, 1, 3, 8};
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout << "Number of bins required in First Fit : " << firstFit(weight1, m, C);
return 0;
}
আউটপুট
Number of bins required in First Fit : 4
First Fit O(m²) টাইম নেয়, কিন্তু Self-Balancing BST দিয়ে O(m log m)-এ করা যায়।
Best Fit
নেক্সট আইটেমকে সবচেয়ে টাইট স্পেসে রাখা হয় (সর্বনিম্ন খালি জায়গা থাকে এমন বিনে)।
C++ ইমপ্লিমেন্টেশন
// C++ program to calculate number of bins required using Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;
int bestFit(int weight1[], int m, int C) {
int res = 0;
int bin_rem[m];
for (int i = 0; i < m; i++) {
int j;
int min = C + 1, bi = 0;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight1[i] && bin_rem[j] - weight1[i] < min) {
bi = j;
min = bin_rem[j] - weight1[i];
}
}
if (min == C + 1) {
bin_rem[res] = C - weight1[i];
res++;
} else
bin_rem[bi] -= weight1[i];
}
return res;
}
int main() {
int weight1[] = {2, 5, 4, 7, 1, 3, 8};
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout << "Number of bins required in Best Fit : " << bestFit(weight1, m, C);
return 0;
}
আউটপুট
Number of bins required in Best Fit : 4
Best Fit-ও Self-Balancing BST দিয়ে O(m log m)-এ করা যায়।
অফলাইন অ্যালগরিদম
সব এলিমেন্ট আগেই থাকে। বড় এলিমেন্টগুলো লেট এসে প্যাকিং কঠিন হয়। সমাধান: ইনপুট সো্র্ট করে বড় এলিমেন্টগুলো আগে রাখা।
First Fit Decreasing
C++ ইমপ্লিমেন্টেশন
// C++ program to find number of bins needed using First Fit Decreasing algorithm.
#include <bits/stdc++.h>
using namespace std;
int firstFit(int weight1[], int m, int C) { /* উপরের কোড */ }
int firstFitDec(int weight1[], int m, int C) {
sort(weight1, weight1 + m, greater<int>());
return firstFit(weight1, m, C);
}
int main() {
int weight1[] = {2, 5, 4, 7, 1, 3, 8};
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout << "Number of bins required in First Fit Decreasing : " << firstFitDec(weight1, m, C);
return 0;
}
আউটপুট
Number of bins required in First Fit Decreasing : 3
First Fit Decreasing স্যাম্পল ইনপুটের জন্য বেস্ট রেজাল্ট দেয়। Self-Balancing BST দিয়ে O(m log m)-এ করা যায়।
