問題描述

一個工廠制造的產品形狀都是長方體，它們的高度都是 h，長和寬都相等，一共有六個型號，他們的長寬分別為 1*1, 2*2, 3*3, 4*4, 5*5, 6*6.? 這些產品通常使用一個? 6*6*h? 的長方體包裹包裝然后郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的包裹數量。他們很需要有一個好的程序幫他們解決這個問題從而節省費用。現在這個程序由你來設計。

輸入數據

輸入文件包括幾行，每一行代表一個訂單。每個訂單里的一行包括六個整數，中間用空

格隔開，分別為 1*1 至 6*6 這六種產品的數量。輸入文件將以 6 個 0 組成的一行結尾。

輸出要求

除了輸入的最后一行 6 個 0 以外，輸入文件里每一行對應著輸出文件的一行，每一行輸

出一個整數代表對應的訂單所需的最小包裹數。

輸入樣例

0 0 4 0 0 1?

7 5 1 0 0 0?

0 0 0 0 0 0?

輸出樣例

2?

1?

?

問題分析：

由題意可知，可

（1）每一個6×6的產品都必須要一個箱子來裝，且每個箱子剛好沒有空位子；

（2）每一個5×5的產品也必須要一個箱子來裝，且每一個裝5×5的?箱子都有11個1×1的產品的空位子（因為剩下規格的 產品裝不下）；

（3）每一個4×4的產品也必須要一個箱子來裝且每一個裝4×4的?箱子剩下5個2×2的產品的空位子。（ps:這里優先考慮裝2×2大規格的產品，當然這里也可以剩下20個1×1的產品的空位子，這里先不考慮，如果沒有2×2規格的產品，再考慮1×1的產品，后面我會統一計算1×1的空位子的個數）

（4）對于3×3的產品，由于每4個3×3的產品才能裝滿一個箱子，所以對于用一個箱子來裝3×3的產品時，空余的位子的情況比較復雜，一共分為四種情況：

? ? ? ? ? ①3×3的產品個數a3剛好是4的倍數，這樣就沒有空位子

? ? ? ? ? ②3×3的產品個數a3是4的倍數還多了1個3×3的產品，這時需要箱子的數量為(a3/4)向上取整，即（a3+3）/4個箱子，且這種不滿的箱子都留下了5個2×2的空位子以及7個1×1的空位子（其余的規格不適合填裝）

? ? ? ? ? ③3×3的產品個數a3是4的倍數還多了2個3×3的產品，這時需要箱子的數量為(a3/4)向上取整，即（a3+3）/4個箱子，且這種不滿的箱子都留下了3個2×2的空位子以及6個1×1的空位子（其余的規格不適合填裝）

? ? ? ? ?④3×3的產品個數a3是4的倍數還多了3個3×3的產品，這時需要箱子的數量為(a3/4)向上取整，即（a3+3）/4個箱子，且這種不滿的箱子都留下了1個2×2的空位子以及5個1×1的空位子（其余的規格不適合填裝）

（4）對于2×2的產品，每9個2×2產品才能填滿一個箱子，根據以上所有情況留下的2×2的空位子數量x，與2×2的產品的數量a2進行比較，如果2×2的產品的數量多于2×2空位子個數，則根據剩下的2×2產品的數量來繼續添加箱子的個數，每9個2×2產品才能填滿一個箱子，這時需要再添加箱子的數量為（a2-x）/9向上取整，即（a2-x+8）/9個箱子，對于一個箱子不足9個2×2產品的，用1×1的產品來填滿。如果2×2的產品的數量小于2×2空位子個數，直接將2×2的產品填入空位子，剩下的空位子全部用1×1的產品來填。

（5）對于1×1的產品，每36個1×1的產品才能裝滿一個箱子，根據以上所有情況留下的1×1的空位子數量y，與1×1的產品的數量a1進行比較，如果1×1的產品的數量多于1×1空位子個數，則根據剩下的1×1產品的數量來繼續添加箱子的個數，每36個1×1產品才能填滿一個箱子，這時需要再添加箱子的數量為(a1-y)/36向上取整，即（a1-y+35）/36 個箱子

綜上可以得出最少需要箱子的個數

c語言源碼：

#include<stdio.h> #include<stdlib.h>int main(){int x,y,cnt; //x為2×2的空位子數量，y為1×1的空位子數量int a1,a2,a3,a4,a5,a6; //6個包裹的大小int c[4]={0,5,3,1}; //當有3×3的時，則2×2的空位子數量可能的個數，這是3×3到2×2的空位子數量的映射while(1){cnt=0;scanf("%d%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5,&a6);if(a1==0&&a2==0&&a3==0&&a4==0&&a5==0&&a6==0)break;cnt+=a6+a5+a4+(a3+3)/4; //a6和a5和a4以及（a3+3）/4都分別占用一個箱子，（a3+3）/4是對a3每滿4向上取整的個數x=5*a4+c[a3%4]; //這是計算2×2空位子的總個數，每一個a4裝的箱子都有著5個2×2的空位子+每一個a3裝的箱子可能存在2×2的空位子數量if(a2>x) //計算a2的數量是否大于其空位子的數量cnt+=(a2-x+8)/9; //計算a2填滿空位子后剩余的a2所需要的箱子的個數。（a2-x+8）/9是對a2每滿9向上取整的箱子個數y=36*cnt-36*a6-25*a5-16*a4-9*a3-4*a2; //計算剩余1×1空位子的個數if(a1>y)//計算a1的數量是否大于其空位子的數量cnt+=(a1-y+35)/36;//計算a1填滿空位子后剩余的a1所需要的箱子的個數.(a1-y+35)/36是對a1每滿36向上取整的箱子個數printf("%d\n",cnt);} return 0; }

?

總結

以上是生活随笔為你收集整理的装箱---一个工厂制造的产品形状都是长方体，它们的高度都是 h，长和宽都相等，一共有六个型号，他们的长宽分别为 1*1, 2*2, 3*3, 4*4, 5*5, 6*6.的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。