POJ 1017

題意：

一個工廠制造的產品形狀都是長方體，它們的高度都是h，長和寬都相等，一共有六個型號，他們的長寬分別為 1*1, 2*2, 3*3, 4*4, 5*5, 6*6.? 這些產品通常使用一個? 6*6*h的長方體包裹包裝然后郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的包裹數量。他們很需要有一個好的程序幫他們解決這個問題從而節省費用。現在這個程序由你來設計。
輸入數據
輸入文件包括幾行，每一行代表一個訂單。每個訂單里的一行包括六個整數，中間用空格隔開，分別為 1*1 至6*6 這六種產品的數量。輸入文件將以 6 個0 組成的一行結尾。

分析：

由于盒子和箱子的高均為h，因此只需考慮底面積的空間。

裝箱問題，貪心解決。

6*6的盒子，每個盒子獨占一個箱子。
5*5的盒子，每個盒子放入一個箱子，該箱子的剩余空間允許放入的最大尺寸為1*1，且最多放11個。
4*4的盒子，每個盒子放入一個箱子，該箱子的剩余空間允許放入的最大尺寸為2*2。
3*3的盒子，每4個剛好獨占一個箱子，不足4個3*3的，剩下空間由2*2和1*2填充。
2*2的盒子和1*1的盒子主要用于填充其他箱子的剩余空間，填充后的多余部分才開辟新箱子裝填。

#include <stdio.h> int main() {int N, a, b, c, d, e, f, x, y;//N箱子數目, y為2*2的空位數目, x為1*1的空位數目。int u[4]={0, 5, 3, 1};//數組u 表示3*3 的產品數目分別是 4的倍數，4 的倍數+1, 4 的倍數+2, 4 的倍數+3//時，為3*3的產品打開的新箱子中剩余的2*2的空位的個數while(1){scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);if (a == 0 && b == 0 && c == 0 && d == 0 && e == 0 && f == 0) break;N = f + e + d + (c + 3) / 4;//c除以4向上取整的結果y = 5 * d + u[c % 4];//每一個4*4的箱子裝過后還可以再裝5個2*2的箱子，//還有3*3的箱子如果沒填滿6*6的箱子的話，也可以用來裝2*2的箱子//如果要裝的2*2的箱子的數目比提供的空間要多，那么多的部分要新開一些箱子if(b > y) N += (b - y + 8 ) / 9;x = 36 * N - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b;//總空位if(a > x) N += ( a - x + 35 ) / 36;printf("%d\n", N);}return 0; }

轉載于:https://www.cnblogs.com/demian/p/6560902.html

總結

以上是生活随笔為你收集整理的POJ 1017 Packets【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

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