โจทย์ Bin Packing (ลดจำนวน Bin ให้น้อยที่สุด) ใน C++

โจทย์ปัญหา

ได้รับ n ชิ้นงานที่มีน้ำหนักต่างกัน และ Bin ที่มีความจุ C ให้จัดชิ้นงานลง Bin ให้น้อยที่สุด (สมมติว่าน้ำหนักทุกชิ้น ≤ C)

ตัวอย่าง

นำเข้า: weights = {4, 1, 8, 1, 4, 2}, C = 10
ผลลัพธ์: 2 bins
การจัด: Bin 1: {4, 4, 2} = 10, Bin 2: {8, 1, 1} = 10

Lower Bound (ขอบล่าง)

จำนวน Bin ขั้นต่ำ ≥ ceil(Total Weight / C)
ตัวอย่าง: ceil(20/10) = 2 bins

Online Algorithms (ชิ้นงานมาทีละชิ้น ต้องจัดทันที)

1. Next Fit - เรียบง่ายที่สุด

ลองใส่ใน Bin ปัจจุบัน ถ้าไม่เข้า → เปิด Bin ใหม่

int nextFit(int weight[], int n, int C) {
    int res = 0, bin_rem = C;
    for (int i = 0; i < n; i++) {
        if (weight[i] > bin_rem) {
            res++;           // Bin ใหม่
            bin_rem = C - weight[i];
        } else {
            bin_rem -= weight[i];
        }
    }
    return res;
}
// Time: O(n), Space: O(1)

2. First Fit - สแกน Bin เก่าทั้งหมด

หา Bin แรกที่ใส่ได้ ถ้าไม่มี → เปิด Bin ใหม่

int firstFit(int weight[], int n, int C) {
    int res = 0;
    vector<int> bin_rem(n, C);  // Max n bins
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < res; j++) {
            if (bin_rem[j] >= weight[i]) {
                bin_rem[j] -= weight[i];
                break;
            }
        }
        if (j == res) {  // ไม่มี Bin ใดใส่ได้
            bin_rem[res] = C - weight[i];
            res++;
        }
    }
    return res;
}
// Time: O(n²), Space: O(n) - ปรับเป็น O(n log n) ด้วย BST ได้

3. Best Fit - ใส่ใน Bin ที่เหลือพอดีที่สุด (เหลือน้อยที่สุด)

int bestFit(int weight[], int n, int C) {
    int res = 0;
    vector<int> bin_rem(n, C);
    for (int i = 0; i < n; i++) {
        int best = -1, min_rem = C + 1;
        for (int j = 0; j < res; j++) {
            if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] < min_rem) {
                min_rem = bin_rem[j] - weight[i];
                best = j;
            }
        }
        if (best == -1) {
            bin_rem[res] = C - weight[i];
            res++;
        } else {
            bin_rem[best] -= weight[i];
        }
    }
    return res;
}
// Time: O(n²), ปรับเป็น O(n log n) ได้ด้วย BST

Offline Algorithms (มีข้อมูลทั้งหมดตั้งแต่แรก)

First Fit Decreasing (FFD) - เรียงใหญ่ไปเล็ก แล้ว First Fit

int firstFitDec(int weight[], int n, int C) {
    sort(weight, weight + n, greater<int>());  // เรียงใหญ่ไปเล็ก
    return firstFit(weight, n, C);             // แล้วค่อย First Fit
}
// ให้ผลดีกว่า Online Algorithms มาก

ผลลัพธ์ตัวอย่าง (weights = {2,5,4,7,1,3,8}, C=10)

คำอธิบายเพิ่มเติม

• Bin Packing เป็น NP-Hard - ไม่มีอัลกอริทึม Polynomial Time ที่หาคำตอบ Optimal ได้เสมอ (เว้นแต่ P=NP)
• FFD ให้ Approximation Ratio ≤ 11/9 OPT + 1
• ใช้ในทางปฏิบัติ: จัดกล่องขนส่ง, จัดตารางโฆษณา, Memory Allocation, Job Scheduling
• สำหรับ Exact Solution ใช้ Branch & Bound หรือ Integer Linear Programming