解題思路:貪心算法。

(1) 6*6的產(chǎn)品每個會占用一個完整的箱子，并且沒有剩余空間

(2) 5*5的產(chǎn)品每個占用一個新的箱子，并且留下 11 個可以盛放 1*1 的產(chǎn)品的剩余空間

(3) 4*4的產(chǎn)品每個占用一個新的箱子，并且留下 5 ?個可以盛放 2*2 的產(chǎn)品的剩余空間

(4)?3*3的產(chǎn)品情況比較復雜，首先3*3 的產(chǎn)品不能放在原來裝有 5*5 或者 4*4 的箱子中，那么必須為3*3 的產(chǎn)品另開若干個新的箱子，新開的箱子數(shù)目等于 3*3 的產(chǎn)品的數(shù)目除以4向上取整(可以使用ceil函數(shù))，同時需要討論為 3*3 的產(chǎn)品新開箱子時，剩余的空間可以盛放多少 2*2 和 1*1 的產(chǎn)品：

① 3*3 的產(chǎn)品的數(shù)目恰好是4的倍數(shù)，此時還剩0個2*2的空位；

② 3*3 的產(chǎn)品數(shù)目是 4 的倍數(shù)加1， 此時還剩5個2*2的空位和7個1*1的空位；

③ 3*3 的產(chǎn)品數(shù)目是 4 的倍數(shù)加2， 此時還剩3個2*2的空位和6個1*1的空位；

④ 3*3 的產(chǎn)品數(shù)目是 4 的倍數(shù)加3， 此時還剩1個2*2的空位和5個1*1的空位；

(5)處理完3*3的產(chǎn)品，就可以比較一下剩余的2*2的空位和2*2產(chǎn)品的數(shù)目，如果產(chǎn)品數(shù)目多，就將 2*2 的空位全部填滿，再為2*2 的產(chǎn)品打開新箱子；

(6)比較一下剩余空間與 1*1 的產(chǎn)品數(shù)目，如果空位多，將1*1的產(chǎn)品全部填入空位即可；否則，先將1*1的空位填滿，然后再為 1*1 的產(chǎn)品打開新的箱子。

注意事項:使用ceil函數(shù)可以實現(xiàn)向上取整。double?ceil(double x); 功 能： 返回大于或者等于指定表達式的最小整數(shù)。注意返回的是一個浮點數(shù)哦。

參考代碼:#include?

#include?

int?main()

{

int?box[7]={0};

int?i,sum,totalbox,space2_num,space1_num;?//totalbox:?需要的箱子數(shù)目，space2_num:2*2?的空位數(shù)目

//?space1_num:?1*1?的空位數(shù)目。

int?space2[4]={0,5,3,1};?//數(shù)組space2表示?3*3?的產(chǎn)品數(shù)目分別是?4的倍數(shù)，4?的倍數(shù)+1,?4?的倍數(shù)+2,

//4的倍數(shù)+3時為3*3的產(chǎn)品打開的新箱子中剩余的?2*2的空位的個數(shù)

while(1)

{

sum=0;

for(i=1;i<=6;i++)

{

scanf("%d",&box[i]);??//輸入?1*1?至?6*6?這六種產(chǎn)品的數(shù)量分別保存在box[1]到?box[6]中

sum=sum+box[i];

}

if(sum==0)?break;

totalbox=box[6]+box[5]+box[4]+ceil(?box[3]?/?4.0?);??//較大的產(chǎn)品只能自己開箱

space2_num=box[4]*5+space2[?box[3]%4?];??//每一個4*4的箱子裝過后還可以再裝5個2*2的箱子

//還有3*3的箱子如果沒填滿6*6的箱子的話，也可以用來裝2*2的箱子

if(box[2]>space2_num)

totalbox+=ceil(?(box[2]-space2_num)?/?9.0?);

space1_num=totalbox*36-(box[6]*36+box[5]*25+box[4]*16+box[3]*9+box[2]*4);

//space1_num存放多出來的面積即1*1的空位數(shù)目

if(box[1]>space1_num)??//空間不夠則新開箱

totalbox+=ceil(?(box[1]-space1_num)?/?36.0?);??//向上取整

printf("%d\n",totalbox);

}

return?0;

}

總結(jié)

以上是生活随笔為你收集整理的装箱问题C语言报告,装包装箱问题 （C语言代码）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。