Java 實現裝箱問題演算法：最小化 6×6 容器數量

問題描述

工廠生產六種長方體產品，高度固定為 h，長寬相等，規格為 1×1、2×2、3×3、4×4、5×5、6×6。產品以 6×6×h 容器包裝郵寄。郵費昂貴，需演算法計算每張訂單所需最少容器數量。

輸入輸出格式

• 輸入：多行，每行 6 個整數（空格分隔），分別對應 1×1 至 6×6 產品數量。以 6 個 0 結尾。
• 輸出：每行輸入對應一行輸出，輸出該訂單所需最小容器數。

演算法核心邏輯

空間佔用規則

• 6×6：一個容器僅能放一個
• 5×5：一個容器僅能放一個，剩餘空間可放 11 個 1×1
• 4×4：一個容器放一個，剩餘空間可放 5 個 2×2（優先放 2×2，不足再轉 1×1）
• 3×3：一容器最多放 4 個。依放入數量不同，剩餘空間可容納不同數量的 2×2 與 1×1：
  • 1 個 3×3 → 剩 5 個 2×2 + 7 個 1×1
  • 2 個 3×3 → 剩 3 個 2×2 + 6 個 1×1
  • 3 個 3×3 → 剩 1 個 2×2 + 5 個 1×1
• 2×2：一容器最多放 9 個
• 1×1：一容器最多放 36 個

貪婪策略流程

1. 基礎容器數 = 6×6 + 5×5 + 4×4 數量
2. 計算 3×3 所需容器：ceil(count_3x3 / 4)
3. 統計上述容器中預留給 2×2、1×1 的剩餘空間
4. 優先填入 2×2，不足空間轉換為 1×1（1 個 2×2 空間 = 4 個 1×1）
5. 剩餘 2×2、1×1 另開新容器：ceil(剩餘2×2 / 9)、ceil(剩餘1×1 / 36)

Java 完整實作

import java.io.BufferedInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BoxPacking {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        Map orders = new HashMap<>();
        int orderIndex = 0;
        
        // 讀取所有訂單
        while (true) {
            int[] qty = new int[6];
            for (int i = 0; i < 6; i++) qty[i] = sc.nextInt();
            
            if (qty[0] == 0 && qty[1] == 0 && qty[2] == 0 
                && qty[3] == 0 && qty[4] == 0 && qty[5] == 0) break;
            
            orders.put(orderIndex++, qty);
        }
        
        // 處理每張訂單
        for (int i = 0; i < orders.size(); i++) {
            int[] v = orders.get(i);
            int boxes = 0;
            
            // 1. 6x6, 5x5, 4x4 各佔一箱
            boxes += v[3] + v[4] + v[5]; // 索引 3,4,5 對應 4x4, 5x5, 6x6
            
            // 2. 3x3 打包
            if (v[2] > 0) {
                boxes += (v[2] + 3) / 4; // 等同 ceil(v[2]/4)
            }
            
            // 3. 計算現有箱子中可用的 1x1 和 2x2 空間
            int space1x1 = v[4] * 11;           // 5x5 剩餘
            int space2x2 = v[3] * 5;            // 4x4 剩餘
            
            // 3x3 放置後的剩餘空間
            switch (v[2] % 4) {
                case 1: space1x1 += 7; space2x2 += 5; break;
                case 2: space1x1 += 6; space2x2 += 3; break;
                case 3: space1x1 += 5; space2x2 += 1; break;
            }
            
            // 4. 盡量填入 1x1
            if (v[0] <= space1x1) {
                v[0] = 0;
            } else {
                v[0] -= space1x1;
            }
            
            // 5. 盡量填入 2x2，不足轉 1x1
            if (v[1] <= space2x2) {
                v[1] = 0;
            } else {
                int deficit2x2 = v[1] - space2x2;
                v[1] = 0;
                // 缺口轉為 1x1 需求 (1 個 2x2 = 4 個 1x1)
                int need1x1 = deficit2x2 * 4;
                if (v[0] <= need1x1) v[0] = 0;
                else v[0] -= need1x1;
            }
            
            // 6. 剩餘產品另開新箱
            if (v[0] > 0 || v[1] > 0) {
                if (v[1] > 0) {
                    boxes += (v[1] + 8) / 9; // 2x2 箱數
                    int lastBoxSpace2x2 = v[1] % 9 == 0 ? 0 : 9 - (v[1] % 9);
                    int convertTo1x1 = lastBoxSpace2x2 * 4;
                    if (v[0] <= convertTo1x1) v[0] = 0;
                    else v[0] -= convertTo1x1;
                }
                if (v[0] > 0) {
                    boxes += (v[0] + 35) / 36; // 1x1 箱數
                }
            }
            
            System.out.println(boxes);
        }
    }
}

關鍵點解析

• 索引對應：陣列索引 0-5 對應 1×1 至 6×6，注意 v[3] 為 4×4，v[4] 為 5×5，v[5] 為 6×6
• 天花板除法：(n + d - 1) / d 實現 ceil(n/d)
• 空間轉換：2×2 空間不足時轉為 1×1 需求 (×4)，體現貪婪策略優先填大件
• 邊界處理：最後一箱 2×2 未滿時，剩餘空間自動轉給 1×1

複雜度分析

• 時間複雜度：O(1) 每訂單，僅固定運算步驟
• 空間複雜度：O(1) 常數空間

測試案例

輸入：
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 4 0 0 0
0 0 0 0 0 0

輸出：
1
1
1
1

分別對應：單個 6×6、單個 5×5、單個 4×4、四個 3×3（恰好一箱）。