# 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 requiredEnd`

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 AlgorithmItems sizes: 4 8 6 5 2 7Bin Capacity: 10Number 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 DecreasingItems sizes: 4 8 6 5 2 7Bin Capacity: 10Number of bins required: 4Bins content:Bin 1: Remaining space = 0Bin 2: Remaining space = 3Bin 3: Remaining space = 0Bin 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.