Chương trình C++ triển khai thuật toán Bin Packing

Bài toán đóng gói thùng (bin packing) là một loại đặc biệt của bài toán cắt khoan (cutting stock). Trong bài toán bin packing, các vật thể có thể tích khác nhau phải được đóng gói vào một số hữu hạn các container hoặc thùng (bins) mỗi thùng có thể tích V theo cách giảm thiểu số lượng thùng sử dụng. Trong lý thuyết độ phức tạp tính toán, đây là một bài toán tổ hợp NP-hard.

Khi số thùng bị giới hạn ở 1 và mỗi vật phẩm được đặc trưng bởi cả thể tích và giá trị, bài toán tối đa hóa giá trị các vật phẩm có thể vừa trong thùng được gọi là bài toán cái ba lô (knapsack problem).

Thuật toán

Bắt đầu
    Binpacking(con trỏ, kích thước, số tập hợp)
    Khai báo bincount, m, i
    Khởi tạo bincount = 1, m = kích thước
    Với i = 0 đến số tập hợp
        Nếu (m - *(a + i) > 0) thực hiện
            m = m - *(a + i)
            Tiếp tục
        Ngược lại
            Tăng bincount
            m = kích thước;
            Giảm i
            In số thùng cần thiết
Kết thúc

Mã ví dụ

#include<iostream> 
using namespace std; 

void binPacking(int *a, int size, int n) { 
    int binCount = 1; 
    int m = size; 
    for (int i = 0; i < n; i++) { 
        if (m - *(a + i) > 0) { 
            m -= *(a + i); 
            continue; 
        } else { 
            binCount++; 
            m = size; 
            i--; 
        } 
    } 
    cout << "Số thùng cần thiết: " << binCount; 
} 

int main(int argc, char **argv) { 
    cout << "Nhập số vật phẩm trong tập: "; 
    int n; 
    cin >> n; 
    cout << "Nhập " << n << " vật phẩm:"; 
    int a[n]; 
    for (int i = 0; i < n; i++) 
        cin >> a[i]; 
    cout << "Nhập kích thước thùng: "; 
    int size; 
    cin >> size; 
    binPacking(a, size, n); 
}

Kết quả

Nhập số vật phẩm trong tập: 3 
Nhập 3 vật phẩm: 4 6 7 
Nhập kích thước thùng: 26 
Số thùng cần thiết: 1