POJ 1017 Packets：貪心裝箱問題經典解法

題目大意

有 1×1、2×2、3×3、4×4、5×5、6×6 六種包裹，需裝入最少數量的 6×6 箱子。每種包裹數量給定，求最少箱子數。

貪心策略

1. 6×6 直接佔一箱。
2. 5×5 佔一箱，剩 11 格 1×1。
3. 4×4 佔一箱，剩 5 個 2×2 位置。
4. 3×3：4 個剛好一箱；餘數對應固定的 2×2 和 1×1 空間（查表 u[4]={0,5,3,1}）。
5. 2×2：9 個一箱；不足用 1×1 填補。
6. 1×1：36 個一箱。

關鍵代碼

int u[4] = {0,5,3,1}; // 3x3 餘數對應的 2x2 空間
ans = f + e + d + (c+3)/4;
Two = 5*d + u[c%4];
if (b > Two) ans += (b - Two + 8) / 9;
One = 36*ans - 36*f - 25*e - 16*d - 9*c - 4*b;
if (a > One) ans += (a - One + 35) / 36;

總結

按尺寸從大到小依次填充，利用固定剩餘空間表，O(1) 計算，是貪心裝箱的教科書級範例。