Bin Packing
The bin packing problem involves packing a set of objects into a minimum number of bins, where each bin has a certain weight capacity.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| // Greedy first-fit algorithm
void packBins(int[] weights, int capacity) {
List<Integer>[] bins = new List[weights.length];
int b = 0;
for (int w: weights) {
if (bins[b] == null || bins[b].stream().mapToInt(i -> i).sum() + w > capacity) {
bins[++b] = new ArrayList();
}
bins[b].add(w);
}
System.out.println(b+1 + " bins used");
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| // Greedy first-fit algorithm
void packBins(vector<int> weights, int capacity) {
vector<vector<int>> bins(weights.size());
int b = 0;
for (int w: weights) {
if (bins[b].empty() || accumulate(bins[b].begin(), bins[b].end(), w) > capacity) {
bins[++b];
}
bins[b].push_back(w);
}
cout << b+1 << " bins used" << endl;
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
| # Greedy first-fit algorithm
def pack_bins(weights, capacity):
bins = [[] for _ in range(len(weights))]
b = 0
for w in weights:
if not bins[b] or sum(bins[b]) + w > capacity:
b += 1
bins.append([])
bins[b].append(w)
print(len(bins), "bins used")
|
The goal is to minimize the number of bins used while respecting bin weight capacities. Approaches include first-fit, next-fit, best-fit etc.
Bin packing applies to resource allocation problems like disk spacing or cutting stock.
The Bin Packing problem is a classic optimization problem. It involves fitting a set of items with different sizes into the fewest number of bins, each with a fixed capacity. The primary objective is to minimize the number of bins used. There are different strategies to solve this problem, such as the First-Fit, Best-Fit, and Next-Fit algorithms. These algorithms have real-world applications in resource allocation, logistics, and memory management.
Example Code in Java
Here’s a simple example using the First-Fit algorithm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.util.ArrayList;
public class BinPacking {
public static void main(String[] args) {
int[] items = { 2, 5, 4, 7, 1, 3, 8 };
int binCapacity = 10;
ArrayList<Integer> bins = new ArrayList<>();
for (int item : items) {
boolean placed = false;
for (int j = 0; j < bins.size(); j++) {
if (bins.get(j) >= item) {
bins.set(j, bins.get(j) - item);
placed = true;
break;
}
}
if (!placed) {
bins.add(binCapacity - item);
}
}
System.out.println("Number of bins used: " + bins.size());
}
}
|
Example Code in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
#include <vector>
int main() {
std::vector<int> items = { 2, 5, 4, 7, 1, 3, 8 };
int binCapacity = 10;
std::vector<int> bins;
for (int item : items) {
bool placed = false;
for (int &bin : bins) {
if (bin >= item) {
bin -= item;
placed = true;
break;
}
}
if (!placed) {
bins.push_back(binCapacity - item);
}
}
std::cout << "Number of bins used: " << bins.size() << std::endl;
}
|
Example Code in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| items = [2, 5, 4, 7, 1, 3, 8]
bin_capacity = 10
bins = []
for item in items:
placed = False
for i in range(len(bins)):
if bins[i] >= item:
bins[i] -= item
placed = True
break
if not placed:
bins.append(bin_capacity - item)
print("Number of bins used:", len(bins))
|
In these examples, we iterate through each item and try to place it in the first bin where it fits. If it doesn’t fit in any existing bin, we create a new bin. This is the First-Fit algorithm, one of the simplest methods to solve the Bin Packing problem.