100 lines
4.2 KiB
C
100 lines
4.2 KiB
C
/*
|
||
Program: min-packing.c (Report comments/bugs to chikh@yuntech.edu.tw)
|
||
Function: 將n個糖磚包裝成一大包，每個糖磚長寬高都是10公分，計算最少面積的包裝紙可打包好。
|
||
運作理念：先對n決定可能的分割方式，每一種分割即決定一種包裝方式。
|
||
例：n = 4 = 1+3 = 2+2 = 1+1+2 = 1+1+1+1，代表可把糖磚包裝為
|
||
a) 僅1排，4個擺成一排
|
||
b) 第1排擺1個、第2排擺3個
|
||
c) 第1排擺2個、第2排擺2個
|
||
d) 第1排擺1個、第2排擺1個、第3排擺2個
|
||
e) 第1排擺1個、第2排擺1個、第3排擺1個、第4排擺1個
|
||
注意上述a)與e)實為等義情況。
|
||
因糖磚總數固定，覆蓋上下面的包裝紙面積相同，不同的包裝方式造成周圍長度有差異。
|
||
若能計算每一種分割對應的擺置方式之週長，則可知哪種分割可得最佳組態，問題即得解。
|
||
Notes: 1) 透過整數分割，另自訂shape資料結構以解決問題所需
|
||
2) 底下程式碼運作皆以磚個數為計量單數，最後才換算為真正的長寬高(公分)
|
||
3) 融入「動態規劃」(dynamic programming)技巧，以dimension[]紀錄目前所知最佳組態
|
||
*/
|
||
|
||
#include <stdio.h>
|
||
|
||
typedef struct { /* 自訂shape資料結構，描述將被包裝的幾何形狀物 */
|
||
int n; /* 所含磚數 */
|
||
int base; /* 該形狀的最大底邊長度 */
|
||
int faces; /* 形狀內糖磚共享接觸面數 */
|
||
int circumference; /* 形狀物最短週長 */
|
||
} shape;
|
||
|
||
int indx = 0; /* 指示堆疊頂端元素位置 */
|
||
int element[100] = {0}; /* 以陣列實作堆疊結構 */
|
||
|
||
/* 底下dimension[i]紀錄糖磚數為i的條件下，目前所知之最佳組態(週長最短者) */
|
||
shape dimension[100] = {{0,0,0,0},{1,1,0,4},{2,2,1,6},{3,3,2,8}}; /* 初始化幾何形狀物的最佳尺寸 */
|
||
|
||
shape bestDimension(int n, shape s) /* 把dimension[n]與傳入的s形狀併接，回傳合併後的組態 */
|
||
{
|
||
shape result; /* 合併後的結果，將作為函數回傳的內容 */
|
||
int minBase;
|
||
|
||
if (s.n == 0) /* s是空的 */
|
||
result = dimension[n];
|
||
else { /* 把dimension[n]與傳入的s併接，決定新的最佳組態 */
|
||
minBase = dimension[n].base <= s.base? dimension[n].base : s.base; /* 計算二個別形狀之底邊最小者，將影響接觸面大小與週長的改變 */
|
||
result.n = n+s.n; /* 合併後的新形狀內含的糖磚數 */
|
||
result.faces = dimension[n].faces+s.faces + minBase; /* 共享接觸面數將增加 */
|
||
result.base = dimension[n].base >= s.base? dimension[n].base : s.base; /* 二個別形狀之底邊最大者為合併後的底邊長度 */
|
||
result.circumference = dimension[n].circumference + s.circumference - 2*minBase; /* 換算合併後的新形狀物之週長 */
|
||
//if ((dimension[result.n].n == 0) || (dimension[result.n].circumference > result.circumference))
|
||
if ((dimension[result.n].n == 0) || (dimension[result.n].circumference > result.circumference)
|
||
|| (dimension[result.n].circumference == result.circumference && dimension[result.n].base < result.base)) /* 若新組態優於dimension[]所記錄內容，則更新 */
|
||
dimension[result.n] = result;
|
||
}
|
||
|
||
//printf("磚數 = %d; 底邊 = %d; 共面數 = %d; 週長 = %d\n",result.n, result.base, result.faces, result.circumference);
|
||
|
||
return result;
|
||
}
|
||
|
||
shape partition(int n, int max, int addend) /* n:待分割的數、max:最大元素、addend:所採用的分解元素 */
|
||
{
|
||
int i;
|
||
shape result = {0,0,0,0}; /* 空的幾何形狀 */
|
||
static shape bestOne = {0,0,0,1000000}; /* 即將回傳的最佳組態，先預設週長為某超大的數值，隨後將更新 */
|
||
|
||
element[indx++] = addend; /* 相當於push()動作 */
|
||
|
||
if (n == 0) { /* 已觸底、無法再分割，把推疊內的內容取出 */
|
||
for (i = indx-1; i > 0; i--) /* 逐一合併所有可能分割所對應的幾何形狀物，結果紀錄於result */
|
||
result = bestDimension(element[i],result);
|
||
//printf("磚數 = %d; 底邊 = %d; 共面數 = %d; 週長 = %d\n",result.n, result.base, result.faces, result.circumference);
|
||
if (bestOne.circumference > result.circumference) bestOne = result;
|
||
}
|
||
else /* n > 0，意味著尚可繼續分割 */
|
||
for (i = 1; i <= max && i <= n; i++)
|
||
partition(n-i,i,i);
|
||
|
||
indx--; /* 等同pop()動作 */
|
||
|
||
return bestOne; /* 回傳最佳形狀 */
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int n, i, numCube;
|
||
shape bestLayout;
|
||
|
||
printf("\n*** 最小包裝面積之郵寄包裹程式 ***\n\n輸入糖磚數 ==> ");
|
||
scanf("%d",&n);
|
||
//printf("\n最少包裝紙面積 = %d\n",partition(n,n,0).circumference*10*10+2*n*10*10);
|
||
bestLayout = partition(n,n,0);
|
||
printf("\n最少包裝紙面積 = %d\n",bestLayout.circumference*10*10+2*n*10*10);
|
||
|
||
printf("\n包裝方式為擺\放若干排：\n");
|
||
for (numCube = n, i = 1; numCube > 0; numCube -= bestLayout.base, i++) {
|
||
bestLayout = dimension[numCube];
|
||
printf("第%d排，擺\%d個磚\n",i,bestLayout.base); /* 輸出留意有"許功蓋"問題，因此多加\以避免困擾 */
|
||
}
|
||
|
||
return 0;
|
||
}
|