【題目鏈接】

ybt 1226：裝箱問題
OpenJudge NOI 4.6 19:裝箱問題

【題目考點(diǎn)】

1. 貪心

【解題思路】

該題說是三維立方體，實(shí)際上無論是包裹還是產(chǎn)品，高度都是h，因而不用考慮高度，這實(shí)際上是二維平面上的問題。

1. 貪心選擇性質(zhì)的證明

貪心選擇：選擇最大的可以裝入該包裹的產(chǎn)品裝入該包裹

證明：存在最優(yōu)解包含第一次的貪心選擇。即存在最優(yōu)解，第一個(gè)包裹中包含最大產(chǎn)品。

假設(shè)所有最優(yōu)解都不包含第一次的貪心選擇，即第一個(gè)包裹C中不包含最大的產(chǎn)品x。
最大的產(chǎn)品x一定存在于某個(gè)包裹內(nèi)，記那個(gè)包裹為N。我們可以將N中的所有產(chǎn)品和C中的所有產(chǎn)品完全交換。總包裹數(shù)量不變，第一個(gè)包裹C中存在產(chǎn)品x，這與假設(shè)相悖，假設(shè)不成立，原命題得證。

證明：前k步都做貪心選擇，存在最優(yōu)解包含第k+1步的貪心選擇。

是否做貪心選擇區(qū)別在于：當(dāng)前拿到一個(gè)最大的可以裝入當(dāng)前包裹C的產(chǎn)品x，是將這個(gè)產(chǎn)品放在當(dāng)前包裹C中，還是將其放在一個(gè)新包裹N中。貪心選擇是將其放在當(dāng)前包裹C中。
使用反證法：假設(shè)對(duì)所有最優(yōu)解，在裝第k+1個(gè)產(chǎn)品時(shí)，當(dāng)前關(guān)注的包裹C可以裝入的最大產(chǎn)品為x，此時(shí)不進(jìn)行貪心選擇，不選擇x，接下來只會(huì)裝入大小小于x的產(chǎn)品。也可以說，當(dāng)前包裹C中，產(chǎn)品x的數(shù)量不會(huì)更多。
下面考慮在N中包括x的部分產(chǎn)品能否和C中的一些產(chǎn)品或空位交換，且兩包裹仍能裝得下。如果可以，那么說明第k+1步進(jìn)行了貪心選擇，選擇了產(chǎn)品x，總包裹數(shù)量不變，也是最優(yōu)解。假設(shè)不成立，原命題得證。

• 如果N中x的數(shù)量大于C中x的數(shù)量，且x在C中與N中都是最大的產(chǎn)品，那么可以將N與C中的所有產(chǎn)品整體交換。
  x為4*4、5*5、6*6都滿足這一情況。或C中3*3的個(gè)數(shù)比N中3*3的個(gè)數(shù)更少。
  例：x為5*5，在第k+1步往C中裝產(chǎn)品時(shí)，沒有按照貪心選擇將5*5的產(chǎn)品裝入C。后來5*5的產(chǎn)品裝入了N，C中又裝了一些產(chǎn)品。將C與N的所有產(chǎn)品交換后，C中存在貪心選擇，總包裹數(shù)仍然最少，說明存在最優(yōu)解在第k+1步進(jìn)行了貪心選擇，假設(shè)不成立，原命題得證。
  
  以下為N中x的數(shù)量小于等于C中x的數(shù)量的情況：
• 如果x是1*1的產(chǎn)品，那么C當(dāng)時(shí)可以放1*1的產(chǎn)品但不放，存在一些位置空著，C中一定有可以放下1*1的空位。可以完成交換。
  
• 如果x是2*2的產(chǎn)品，那么C當(dāng)時(shí)可以放2*2的產(chǎn)品但不放，去放1*1的產(chǎn)品或空著。那么在C中一定可以選擇出2*2的區(qū)域，其中可以是1*1的產(chǎn)品也可以是空位，與x進(jìn)行交換。
  
• 如果x是3*3的產(chǎn)品，說明先前加入C的是若干個(gè)3*3的產(chǎn)品。

如果C中已經(jīng)有3個(gè)3*3的產(chǎn)品，剩下3*3的位置，這部分位置的產(chǎn)品或空位都可以與x進(jìn)行交換。

如果C中已經(jīng)有2個(gè)3*3的產(chǎn)品，且剩余的空間中擺了至多3個(gè)2*2的產(chǎn)品。
N中有2個(gè)3*3產(chǎn)品與至多3個(gè)2*2產(chǎn)品，此時(shí)，把N中的1個(gè)3*3與C中的2個(gè)2*2與1個(gè)1*1交換，結(jié)果為C中有3個(gè)3*3與1個(gè)2*2，N中有1個(gè)3*3與5個(gè)2*2，這種交換是可行的。
同理，如果N中有1個(gè)3*3與至多5個(gè)2*2，用N中的1個(gè)3*3交換C中的2個(gè)2*2與1個(gè)1*1是可行的。
例：將N中的紅色3*3產(chǎn)品x與C中的藍(lán)色兩個(gè)2*2產(chǎn)品與1個(gè)1*1產(chǎn)品進(jìn)行交換。交換 后一些1*1產(chǎn)品位置發(fā)生變化。

如果C中已經(jīng)有1個(gè)3*3產(chǎn)品，剩余空間擺了至多5個(gè)2*2的產(chǎn)品。N中有1個(gè)3*3產(chǎn)品與至多5個(gè)2*2的產(chǎn)品，用N中的1個(gè)3*3交換C中的2個(gè)2*2與1個(gè)1*1是可行的。
如果待交換的產(chǎn)品沒有那么多，可以用空位代替。
例：將N中的紅色3*3產(chǎn)品x與C中的藍(lán)色兩個(gè)2*2產(chǎn)品與1個(gè)1*1產(chǎn)品進(jìn)行交換。交換 后一些1*1產(chǎn)品位置發(fā)生變化。

• x不可能是4*4或更大的產(chǎn)品，如果是，C中可以放x但不放，C中的x只能是0個(gè)，而N中的x有1個(gè)，這是前面已經(jīng)討論過的“如果N中x的數(shù)量大于C中x的數(shù)量”的情況。
  因此N中包括x的部分產(chǎn)品總能和C中的一些產(chǎn)品或空位交換位置。說明第k+1步進(jìn)行了貪心選擇，選擇了產(chǎn)品x，總包裹數(shù)量不變，也是最優(yōu)解。因而假設(shè)不成立，原命題得證。

2. 具體做法

考慮各種情況下，剩下的空間最多可以放下幾個(gè)各種產(chǎn)品，總結(jié)成表格

已有最多放幾個(gè)3*3最多放幾個(gè)2*2最多放幾個(gè)1*1

1個(gè)6*6	0	0	0
1個(gè)5*5	0	0	11
1個(gè)4*4	0	5	20
1個(gè)3*3	3	5	27
2個(gè)3*3	2	3	18
3個(gè)3*3	1	1	9
無	4	9	36

此這基礎(chǔ)上，每多放一個(gè)2*2，1*1可放個(gè)數(shù)減4。
觀察規(guī)律，1*1可以放的個(gè)數(shù)就是總面積6*6減去所有放入其中的產(chǎn)品的總面積。
在已有3*3的情況下，每多放入一個(gè)3*3，2*2可以放入的個(gè)數(shù)減2。
這里只需要設(shè)數(shù)組記錄放入1個(gè)某大小產(chǎn)品后，其他大小產(chǎn)品可以放入的數(shù)量。

從大到小遍歷各個(gè)產(chǎn)品，找到一個(gè)產(chǎn)品，開一個(gè)新包裹將其放入。如果剩余位置還可以放產(chǎn)品，那么放入對(duì)應(yīng)產(chǎn)品，改變剩余位置可放產(chǎn)品的數(shù)量。直到?jīng)]有位置可放或沒有足夠的產(chǎn)品可放為止。再?gòu)拇蟮叫≌蚁乱粋€(gè)產(chǎn)品，開一個(gè)新包裹將其放入。重復(fù)上述過程，直到看完所有產(chǎn)品為止。

【題解代碼】

解法1：貪心（本人原創(chuàng)）

#include <bits/stdc++.h> using namespace std; int status[8][4];//status[i][j]:包裹中已有1個(gè)大小為i*i的產(chǎn)品，此時(shí)可以最多放入多少個(gè)j*j的產(chǎn)品 void initStatus() {//status[0]:包裹中沒有產(chǎn)品時(shí)，各種產(chǎn)品最多可以放多少個(gè) status[2][2] = 8;status[3][2] = 5, status[3][3] = 3;status[4][2] = 5;for(int i = 1; i <= 6; ++i)status[i][1] = 36 - i*i; } int pro[8];//pro[i]:i*i產(chǎn)品的數(shù)量 int main() {initStatus(); while(true){int sum = 0, bag = 0, rem[8];//sum:總產(chǎn)品數(shù)量 bag:包裹數(shù) rem[i]:當(dāng)前剩余空間能放幾個(gè)i*i for(int i = 1; i <= 6; ++i){cin >> pro[i];sum += pro[i];}if(sum == 0)//如果6個(gè)數(shù)都是0，那么加和為0，要跳出循環(huán) break;for(int i = 6; i >= 1; --i){while(pro[i] > 0){bag++;//用一個(gè)新包裹放i*ipro[i]--;for(int j = 1; j <= 3; ++j)//獲取當(dāng)前剩余空間情況 rem[j] = status[i][j];int j = 3;while(j >= 1){if(rem[j] > 0 && pro[j] > 0)//如果可以放j*j的產(chǎn)品 {pro[j]--;//放一個(gè)產(chǎn)品 if(j == 3){rem[3]--;rem[2] -= 2;rem[1] -= 9;}else if(j == 2){rem[2]--;rem[1] -= 4;}else//j == 1rem[1]--;}else--j;}} }cout << bag << endl;} return 0; }

解法2：手動(dòng)完成貪心過程

思路來自zqhf123博客：zqhf123 1226：裝箱問題
由于箱子種類不多，我們可以手動(dòng)完成每一步的貪心行為。先裝大產(chǎn)品，看占了多少空間，剩下多少空間。再看小產(chǎn)品。逐次算出當(dāng)前可以給下一個(gè)產(chǎn)品留出的空位。

#include<bits/stdc++.h> using namespace std; int bag;//總包裹數(shù) int k[4] = {0, 5, 3, 1};//k[i]表示3*3的產(chǎn)品有i個(gè)時(shí)（k[0]表示有4個(gè)時(shí)）剩余空間可以放2*2產(chǎn)品的個(gè)數(shù) int pro[8], p2, p1;//p2:2*2空位數(shù) p1:1*1空位數(shù) int main() { while(true){for(int i = 1; i <= 6; ++i)cin >> pro[i];if(pro[1] == 0 && pro[2] == 0 && pro[3] == 0 && pro[4] == 0 && pro[5] == 0 && pro[6] == 0) break;bag = pro[6] + pro[5] + pro[4] + ceil(pro[3]/4.0);//6*6和5*5和4*4一定是一個(gè)占一個(gè)箱子，而3*3 4個(gè)占一個(gè)箱子p2 = 5*pro[4]+k[pro[3]%4];//k[pro[3]%4]：有pro[3]%4個(gè)3*3在一個(gè)包裹中時(shí)，剩下的位置可以放2*2的數(shù)目 if(pro[2] > p2)//2*2的個(gè)數(shù)比我們留出來為2*2的空間個(gè)數(shù)多，就需要為2*2另開箱子bag += ceil((pro[2]-p2)/9.0);//多出來的2*2箱子應(yīng)該占用的新箱子數(shù) p1 = 36*bag-36*pro[6]-25*pro[5]-16*pro[4]-9*pro[3]-4*pro[2];//求出當(dāng)前包裹中所有剩下的可以放1*1的位置數(shù) if(pro[1] > p1)//如果1*1的個(gè)數(shù)，比我們留出的空間多就需要另開空間 bag += ceil((pro[1]-p1)/36.0);//將多出來的另開箱子 cout << bag << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1226：装箱问题 | OpenJudge NOI 4.6 19:装箱问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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