題目描述

? ? ? ? 一個工廠制造的產品形狀都是長方體，它們的高度都是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)放3*3，4*4，5*5，6*6

? ? ? ? ?(2)用1*1填充放5*5箱子的剩余空間

? ? ? ? ?(3)先用2*2填充放4*4箱子的剩余空間，再用1*1填充放4*4箱子的剩余空間

? ? ? ? ?(4)先用2*2填充放3*3箱子的剩余空間，再用1*1填充放3*3箱子的剩余空間

? ? ? ? ?(5)把4個1*1看作1個2*2，最后多出來的1*1也看作1個2*2，這樣就把所有的1*1轉化成2*2

? ? ? ? ?(6)放剩余的2*2

#include <iostream>using namespace std;int a, b, c, d, e, f; int ans;int main() {int tmp;while(cin >> a >> b >> c >> d >> e >> f && (a || b || c || d || e || f)){ans = (c + 3) / 4 + d + e + f;a = max(0, a - e * 11);tmp = max(0, d * 5 - b);b = max(0, b - d * 5);a = max(0, a - tmp * 4);c %= 4;if(c){tmp = max(0, (5 - (c - 1) * 2) - b);b = max(0, b - (5 - (c - 1) * 2));a = max(0, a - tmp * 4);a = max(0, a - (7 - (c - 1) * 2));}ans += ((a + 3) / 4 + b + 8) / 9;cout << ans << "\n";}return 0; 參考程序

?

? ? ? ? ?根據上面我們可以看出，2*2只需要用來填充放4*4和3*3的箱子，那我們也可以先算出填充完后剩余的2*2還需要多少個箱子。此時我們先更新$ans$。

? ? ? ? 容易想到，其實1*1需要填充的數量也就是$ans \times 36$再減去其它大小產品所占的空間。我們最后再加上填充完后剩余的1*1還需要多少個箱子即可。

#include <iostream>using namespace std;const int t[4] = {0, 5, 3, 1}; int a, b, c, d, e, f; int ans;int main() {int tmp;while(cin >> a >> b >> c >> d >> e >> f && (a || b || c || d || e || f)){ans = f + e + d + (c + 3) / 4;ans += (max(0, b - d * 5 - t[c % 4]) + 8) / 9;ans += (max(0, a - ans * 36 + b * 4 + c * 9 + d * 16 + e * 25 + f * 36) + 35) / 36;cout << ans << "\n";}return 0; } 參考程序

?

?

轉載于:https://www.cnblogs.com/kcn999/p/10925435.html

總結

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

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