Problem 311 Packets，最少包裝箱

這題是考你的邏輯以及空間概念，其實不難，以下會有分析。

我是先宣告兩個整數陣列，residual[6], packets[6];，分別存放各產品的多餘空間數以及使用空間數。再來讀入所有產品的使用空間數，並且判斷所有產品是否為 0：

int i, isZero = 1, total = 0;
for (i = 0; i < 6; i ++)
{
    scanf("%d", &packets[i]);
    residual[i] = 0;
    if (packets[i] != 0)
       isZero = 0;
}
if (isZero) break;

接下來就是重點了，我們必須將 6*6 的箱子妥善分配空間，方能使所耗箱子量減到最低。

在讀入所有產品數量後，可以想見，規格 6*6 的產品必須以一個箱子來包裝，所以箱子總數就必須先加上這個數量：

total += packets[5];

規格 5*5 的產品也必須以一個箱子來包裝，但是會產生 11 個規格 1*1 產品的空間，如以下表格顯示：

X	X	X	X	X	O
X	X	X	X	X	O
X	X	X	X	X	O
X	X	X	X	X	O
X	X	X	X	X	O
O	O	O	O	O	O

所以程式可以這樣寫：

total += packets[4];
residual[0] += packets[4] * 11;

規格 4*4 的產品必須以一個箱子來包裝，但是會產生 5 個規格 2*2 產品的空間。(以下就不提供表格，自行畫圖想像)，所以：

total += packets[3];
residual[1] += packets[3] * 5;

規格 3*3 的產品以 4 個為一箱來包裝。若有剩餘 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 產品的空間，以此觀念寫成以下程式：

total += packets[2] / 4;
packets[2] %= 4, residual[2] = packets[2];
if (residual[2] == 1)
   residual[2] = 0, residual[0] += 7, residual[1] += 5, total ++;
else if (residual[2] == 2)
   residual[2] = 0, residual[0] += 6, residual[1] += 3, total ++;
else if (residual[2] == 3)
   residual[2] = 0, residual[0] += 5, residual[1] += 1, total ++;

接下來只需將 2*2 多餘空間去和使用空間數比較大小，若多餘空間數比較大，則將多餘空間數轉移給規格 1*1 產品使用；若使用空間比較大，則視它能裝幾箱大小，再把多餘的位置轉移給規格 1*1 的產品使用：

if (residual[1] >= packets[1])
   residual[1] -= packets[1], packets[1] = 0;
else
   packets[1] -= residual[1], residual[1] = 0;
total += packets[1] / 9;
packets[1] %= 9;
if (packets[1] > 0)
   residual[0] += 36 - packets[1] * 4, packets[1] = 0, total ++; 
else residual[0] += residual[1] * 4, residual[1] = 0;

而規格 1*1 產品就不需再轉移給空間更小的產品了，只需老老實實的算出它還能裝幾箱大小，如有剩餘，就多一箱：

if (residual[0] >= packets[0])
   residual[0] -= packets[0], packets[0] = 0;
else
   packets[0] -= residual[0], residual[0] = 0;
total += packets[0] / 36;
packets[0] %= 36;
if (packets[0] > 0)
   total ++;

最後只需將total印出即可。
By David.K

p311題目連結
回ACM題庫目錄
回首頁