C++ program to implement the bin packing algorithm
The objective of the classic optimization problem is known as the bin packing algorithm. It is used to efficiently pack items of varying sizes into a predetermined number of bins while minimizing the amount of wasted space. The First Fit Decreasing (FFD) algorithm is one popular way to solve this problem. There are other approaches as well.
Cutting stock problems come in a unique form with the bin packing problem. In order to minimize the number of bins used, objects of varying volumes must be packed into a finite number of containers or bins, each of volume V. It is a combinational NP-hard problem according to the computational complexity theory. The knapsack problem is the problem of maximizing the value of items that can fit in the bin when there is only one bin available, and each item has a volume and a value.
Algorithm:
Let us take a look of the bin packing algorithm in C++:
Begin
Binpacking(pointer, size, no of sets)
Declare bincount, x, i
Initialize bincount = 1, x=size
For i = 0 to number of sets
if (x - *(a + i) > 0) do
x = x - *(a + i)
Continue
Else
Increase bincount
x = size;
Decrement i
Print number of bins required
End
Example:
Let us take an example to illustrate the bin packing algorithm in C++.
#include <iostream>
void Binpacking(int* a, int size, int numOfSets) {
int binCount = 1;
int m = size;
for (int i = 0; i < numOfSets; ++i) {
if (m - *(a + i) >= 0) {
m -= *(a + i);
continue;
} else {
// Start a new bin
binCount++;
m = size;
i--; // Decrement i to consider the current item in the new bin
}
}
// Print the result
std::cout << "Number of bins required: " << binCount << std::endl;
}
int main() {
// Example usage
int items[] = {4, 8, 6, 5, 2, 7};
int binCapacity = 10;
int numOfSets = sizeof(items) / sizeof(items[0]);
std::cout << "Bin Packing Algorithm" << std::endl;
std::cout << "Items sizes: ";
for (int i = 0; i < numOfSets; ++i) {
std::cout << items[i] << " ";
}
std::cout << "\nBin Capacity: " << binCapacity << std::endl;
// Call the bin packing function
Binpacking(items, binCapacity, numOfSets);
return 0;
}
Output:
Bin Packing Algorithm
Items sizes: 4 8 6 5 2 7
Bin Capacity: 10
Number of bins required: 5
Example 2:
Let us take another example to illustrate the bin packing algorithm using the First Fit algorithm in C++.
#include <iostream>
#include <vector>
#include <algorithm>
void firstFitDecreasing(std::vector<int>& items, int binCapacity) {
std::sort(items.begin(), items.end(), std::greater<int>());
std::vector<int> bins;
int binCount = 0;
for (int i = 0; i < items.size(); ++i) {
bool placed = false;
for (int j = 0; j < binCount; ++j) {
if (bins[j] >= items[i]) {
bins[j] -= items[i];
placed = true;
break;
}
}
if (!placed) {
bins.push_back(binCapacity - items[i]);
binCount++;
}
}
std::cout << "Number of bins required: " << binCount << std::endl;
std::cout << "Bins content:" << std::endl;
for (int i = 0; i < binCount; ++i) {
std::cout << "Bin " << i + 1 << ": Remaining space = " << bins[i] << std::endl;
}
}
int main() {
// Example usage
std::vector<int> items = {4, 8, 6, 5, 2, 7};
int binCapacity = 10;
std::cout << "Bin Packing Algorithm using First Fit Decreasing" << std::endl;
std::cout << "Items sizes: ";
for (int item : items) {
std::cout << item << " ";
}
std::cout << "\nBin Capacity: " << binCapacity << std::endl;
firstFitDecreasing(items, binCapacity);
return 0;
}
Output:
Bin Packing Algorithm using First Fit Decreasing
Items sizes: 4 8 6 5 2 7
Bin Capacity: 10
Number of bins required: 4
Bins content:
Bin 1: Remaining space = 0
Bin 2: Remaining space = 3
Bin 3: Remaining space = 0
Bin 4: Remaining space = 5
Conclusion:
In conclusion, the bin packing algorithm is an efficient way to pack items of different sizes into a fixed number of bins while minimizing wasted space. It is a classic optimization problem in C++. In this example, we used two distinct methods: the First Fit Decreasing algorithm and the Next Fit algorithm. In the First Fit Decreasing algorithm, the items are sorted in descending order and deposited in the first bin, which is enough for them, while in the Next Fit approach, a new bin is started whenever the current item doesn't fit into the bin's remaining space. These algorithms provide practical solutions in real-world situations where effective resource allocation is required. We can select or modify these algorithms to balance packing efficiency and computational complexity, depending on the particular requirements of a given problem.