Bài toán Bin Packing (Tối thiểu số bin) trong C++

Cho m phần tử với trọng lượng khác nhau và bin dung lượng C. Gán mỗi phần tử vào bin sao cho số bin dùng tối thiểu. Giả định trọng lượng phần tử < dung lượng bin.

Ứng dụng

• Đặt dữ liệu trên nhiều đĩa.
• Xe tải container.
• Quảng cáo trong khung giờ radio/TV cố định.
• Lập lịch công việc.

Ví dụ

Input: weight[] = {4, 1, 8, 1, 4, 2}, Bin Capacity c = 10
Output: 2
Cần ít nhất 2 bin: Bin 1 {4,4,2}, Bin 2 {8,2}

Giới hạn dưới (Lower Bound)

Số bin tối thiểu ≥ ceil(Tổng trọng lượng / Dung lượng bin). Ví dụ: ceil(20/10) = 2.

Thuật toán Online (phần tử đến lần lượt)

Next Fit

Xét phần tử tiếp theo, nếu vừa bin hiện tại thì đặt, không thì mở bin mới.

// 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;
}

Kết quả: 4 bin. Next Fit O(m) thời gian, O(1) không gian.

First Fit

Quét các bin đã có theo thứ tự, đặt vào bin đầu tiên vừa. Nếu không bin nào vừa → mở bin mới.

// 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;
}

Kết quả: 4 bin. O(m²) thời gian, có thể O(m log m) với cây cân bằng.

Best Fit

Đặt vào bin để lại ít không gian trống nhất (vừa nhất).

// 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 min = C + 1, bi = 0;
        for (int 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;
}

Kết quả: 4 bin. Cũng có thể O(m log m) với cây cân bằng.

Thuật toán Offline (có sẵn tất cả phần tử)

Sắp xếp giảm dần, đặt phần tử lớn trước → First Fit Decreasing.

// First Fit Decreasing
#include <bits/stdc++.h>
using namespace std;

int firstFit(int weight1[], int m, int C) { /* ... như trên ... */ }

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;
}

Kết quả: 3 bin – tốt nhất cho ví dụ này. O(m log m) với cây cân bằng.