裝箱問題：First-Fit 策略模擬與實作

問題描述

有 n 項物品，大小分別為 s1, s2, ..., sn（整數，1 ≤ si ≤ 100）。需將它們裝入容量為 100 的箱子（編號 1~n），採用 **First-Fit 策略**：對每項物品，依序掃描所有箱子，放入**第一個**能容納它的箱子。輸出每個物品所在的箱子編號，以及總共使用的箱子數目。

輸入輸出範例

輸入：
8
60 70 80 90 30 40 10 20

輸出：
60 1
70 2
80 3
90 4
30 1
40 5
10 1
20 2
所需的箱子數目為5

演算法邏輯

• 維護一個陣列 box[] 記錄每個箱子的**剩餘容量**，初始皆為 100。
• 對每個物品 si，從箱子 1 開始遍歷，找到第一個 box[j] >= si 的箱子。
• 將物品放入：box[j] -= si，記錄該物品的箱子編號。
• 若所有現有箱子都裝不下，開啟新箱子（編號遞增）。

C++ 參考實作

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int a[1005], box[1005];
        for (int i = 0; i < n; ++i) cin >> a[i];

        int boxCnt = 0;
        for (int i = 0; i < n; ++i) {
            int item = a[i];
            int placed = 0;
            for (int j = 1; j <= boxCnt; ++j) {
                if (box[j] >= item) {
                    box[j] -= item;
                    cout << item << ' ' << j << '\n';
                    placed = 1;
                    break;
                }
            }
            if (!placed) {
                ++boxCnt;
                box[boxCnt] = 100 - item;
                cout << item << ' ' << boxCnt << '\n';
            }
        }
        cout << "所需的箱子數目為" << boxCnt << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(n × m)，m 為箱子數（最壞情況 m ≈ n），n ≤ 1000 完全足夠。
• 空間：O(n)。

延伸思考

• Best-Fit：放入剩餘空間最小但能容納的箱子，通常空間利用率較高。
• Worst-Fit：放入剩餘空間最大的箱子。
• 離線演算法：先將物品排序（如遞減），再套用 First-Fit，即 **First-Fit Decreasing (FFD)**，近似比更好。

總結

First-Fit 是線上封裝問題的經典啟發式演算法，實作簡單、直觀，適合作為基準比較。實際應用中可根據物品分佈特性選擇更優策略。