POJ1017 Packets

2019-11-06 06:25:22

字體：大中小

供稿：網(wǎng)友

大致題意

工廠生產(chǎn)以相同高度h并且尺寸為1 * 1，2 * 2，3 * 3，4 * 4,5 * 5,6 * 6的方形包裝包裝的產(chǎn)品。這些產(chǎn)品始終以與產(chǎn)品相同的高度h和尺寸6 * 6的正方形包裹交付給客戶。（來自google翻譯）然后題目要求用最少數(shù)量的包裹裝載這些產(chǎn)品。

解題步驟

由于產(chǎn)品規(guī)格較少可以直接暴力求解，將產(chǎn)品按產(chǎn)品規(guī)格從大到小裝入包裹，在裝大規(guī)格產(chǎn)品的同時將小規(guī)格產(chǎn)品”塞入空隙“，這樣可以達到包裹數(shù)量最小的目的。假設(shè)所用包裹數(shù)量no(初始no=0)，a[1]…a[6]代表相應(yīng)規(guī)格（1*1…6*6）產(chǎn)品的數(shù)量。

處理規(guī)格6*6，no = a[6]處理規(guī)格5*5，no+=a[5]，一個包裹只能裝一個5*5規(guī)格的產(chǎn)品，并且產(chǎn)生11個1*1的空隙。因此由1*1規(guī)格的產(chǎn)品來填充：a[1] = a[1] - a[5]*11;處理規(guī)格4*4，no+=a[4]，一個包裹只能裝一個4*4規(guī)格的產(chǎn)品，并且產(chǎn)生的空隙可以由5個4*4規(guī)格的產(chǎn)品填充：a[2] = a[2] - a[4]*5，若a[2]<0，表示還有空隙，由1*1規(guī)格的產(chǎn)品來填充：a[1] = a[1]+a[2]*4（a[2]<0）。處理規(guī)格3*3，no+=ceil(a[3]/4.0)，注意向上取整。一個包裹只能裝4個3*3規(guī)格的產(chǎn)品。此時a[3] = a[3] - (a[3]/4)*4。此時a[3]取值可以是:0,1,2,3。表示最后一個包裹剛好裝滿或只裝了1或2或3個產(chǎn)品，然后剩余空隙可以裝1*1，2*2 規(guī)格產(chǎn)品數(shù)量如下所示，根據(jù)表格再做相應(yīng)處理，處理見代碼部分

已裝3*3個數(shù)	可裝1*1個數(shù)	可裝2*2 個數(shù)
1	7	5
2	6	3
3	8	1

5. 處理規(guī)格2*2，若a[2]>0，no+=ceil(a[2]/9.0)，此時a[2] = a[2] - (a[2]/9)*9，若a[2]<0，表示2*2規(guī)格不能將包裹裝滿，則由1*1規(guī)格的產(chǎn)品來填充，a[1] = a[1] - (36 + 4*a[2])。 6. 處理規(guī)格1*1，若a[1]>0，則no+=ceil(a[1]/36.0)。

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>// 暴力求解int main(){ int a[7],no,i,j,min,temp,temp2; while(1){ memset(a,0,sizeof(a)); no = 0; for(i=1;i<=6;i++) { scanf("%d",&a[i]); } if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0) break; no+=a[6]; no+=a[5]; temp = a[1] - a[5]*11; if(temp>0) a[1] = temp; else a[1] = 0; no+=a[4]; temp = a[2] - a[4]*5; if(temp>0) a[2] = temp; else{ a[2] = 0; temp2 = 0; temp2 = a[1] + 4*temp; //temp<=0 if(temp2>0) a[1] = temp2; else{ a[1] = 0; } } no = no + ceil(a[3]/4.0); temp = a[3] - (a[3]/4)*4; if(temp==0){ a[3] = 0; }else if(temp==1){ a[2] = a[2] - 5; a[1] = a[1] - 7; }else if(temp==2){ a[2] = a[2] - 3; a[1] = a[1] - 6; }else if(temp==3){ a[2] = a[2] - 1; a[1] = a[1] - 8; } if(a[2]<0) a[2] = 0; if(a[1]<0) a[1] = 0; no = no + ceil(a[2]/9.0); temp = a[2] - (a[2]/9)*9; if(temp>0){ temp2 = 36 - 4*temp; a[1] = a[1] - temp2; } if(a[1]>0) no = no + ceil(a[1]/36.0);