โปรแกรม C++ ใช้ Bin Packing Algorithm

ปัญหา Bin Packing เป็นประเภทพิเศษของ Cutting Stock Problem ในปัญหา Bin Packing วัตถุที่มีปริมาตรต่างกันต้องถูกบรรจุลงในจำนวนจำกัดของภาชนะหรือถัง (bins) แต่ละอันมีปริมาตร V โดยที่จำนวนถังที่ใช้น้อยที่สุด ในทฤษฎีความซับซ้อนทางคอมพิวเตอร์ เป็นปัญหา NP-hard แบบ combinational

เมื่อจำนวนถังจำกัดที่ 1 และแต่ละรายการมีทั้งปริมาตรและค่า ปัญหาการเพิ่มค่าสูงสุดของรายการที่ใส่ในถังได้ เรียกว่า Knapsack Problem

อัลกอริทึม

Begin
    Binpacking(pointer, size, no of sets)
    ประกาศ bincount, m, i
    กำหนด bincount = 1, m = size
    For i = 0 ถึงจำนวนเซ็ต
        ถ้า (m - *(a + i) > 0) ทำ
            m = m - *(a + i)
            Continue
        มิฉะนั้น
            เพิ่ม bincount
            m = size;
            ลด i ลง 1
        จบ if
    จบ for
    พิมพ์จำนวนถังที่ต้องการ
End

ตัวอย่างโค้ด

#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 << "Number of bins required: " << binCount;
}

int main(int argc, char **argv) {
    cout << "Enter the number of items in Set: ";
    int n;
    cin >> n;
    cout << "Enter " << n << " items:";
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << "Enter the bin size: ";
    int size;
    cin >> size;
    binPacking(a, size, n);
}

ผลลัพธ์

Enter the number of items in Set: 3
Enter 3 items:4 6 7
Enter the bin size: 26
Number of bins required: 1