一、題目

Description

A factory produces products packed in square packets of the same height h and of the sizes 11, 22, 33, 44, 55, 66. These products are always delivered to customers in the square parcels of the same height h as the products have and of the size 6*6. Because of the expenses it is the interest of the factory as well as of the customer to minimize the number of parcels necessary to deliver the ordered products from the factory to the customer. A good program solving the problem of finding the minimal number of parcels necessary to deliver the given products according to an order would save a lot of money. You are asked to make such a program.

Input

The input file consists of several lines specifying orders. Each line specifies one order. Orders are described by six integers separated by one space representing successively the number of packets of individual size from the smallest size 11 to the biggest size 66. The end of the input file is indicated by the line containing six zeros.

Output

The output file contains one line for each line in the input file. This line contains the minimal number of parcels into which the order from the corresponding line of the input file can be packed. There is no line in the output file corresponding to the last ``null'' line of the input file.

Sample Input

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

Sample Output

2
1

二、思路&心得

• 題目大意為共有1 * 1、2 * 2...6 * 6的產(chǎn)品各a[i]個(gè)，包裝袋大小固定為6 * 6，問(wèn)最少最要多少個(gè)包裝袋，可以把每個(gè)訂單中所有產(chǎn)品包裝起來(lái)。
• 這個(gè)題目有點(diǎn)類似硬幣問(wèn)題，在選擇時(shí)從最大的6 * 6的產(chǎn)品開(kāi)始依次往小進(jìn)行計(jì)算。對(duì)于6 * 6、5 * 5、4 * 4的產(chǎn)品，各需要包裝袋a[6]、a[5]、a[4]個(gè)，其中放置5 * 5產(chǎn)品的包裝袋可以額外裝11個(gè)1 * 1的產(chǎn)品，放置4 * 4產(chǎn)品的可以額外裝5個(gè)2 * 2的產(chǎn)品；對(duì)于3 * 3的產(chǎn)品比較特殊，對(duì)4取模后，根據(jù)余數(shù)0、1、2、3分四種情況進(jìn)行判斷，每次選擇時(shí)盡可能得裝入更多的2 * 2的產(chǎn)品再裝入1 * 1的產(chǎn)品；對(duì)于2 * 2和1 * 1的產(chǎn)品判斷較為簡(jiǎn)單，不再多說(shuō)。
• 在做這題時(shí)剛開(kāi)始有點(diǎn)看不懂題意，便看了下discuss區(qū)，發(fā)現(xiàn)所有人都說(shuō)這題非常非常難以及細(xì)節(jié)很多，導(dǎo)致不敢輕易下手。但是思路想清，WA了一兩次之后，便AC了，好像也沒(méi)想象中的那么難。
• 在網(wǎng)上觀摩到大神的極短代碼，算法思想非常精辟，特另附上，以供學(xué)習(xí)。

三、代碼

我的渣解法：

#include<cstdio>int a[7];int ans;void solve() {ans += (a[4] + a[5] + a[6]);a[1] -= a[5] * 11;a[2] -= a[4] * 5;if (a[2] < 0) {a[1] += a[2] * 4;}ans += (a[3] / 4 + 1);switch (a[3] % 4) {case 0: {ans --;break;}case 1: {if (a[2] > 0) {a[2] -= 5;if (a[2] < 0) {a[1] += a[2] * 4;}a[1] -= 7;} else {a[1] -= 27;}break;} case 2: {if (a[2] > 0) {a[2] -= 3;if (a[2] < 0) {a[1] += a[2] * 4;}a[1] -= 6;} else {a[1] -= 18;}break;}case 3: {if (a[2] > 0) {a[2] -= 1;a[1] -= 5;} else {a[1] -= 9;}break;}}if (a[2] > 0) {ans += a[2] / 9;if (a[2] % 9 > 0) {ans ++;a[1] -= (9 - a[2] % 9) * 4; }}if (a[1] > 0) {ans += (a[1] + 35) /36;}printf("%d\n", ans); }int main () {while (1) {ans = 0;for (int i = 1; i <= 6; i ++) {scanf("%d", &a[i]);}if (!a[1] && !a[2] && !a[3] && !a[4] && !a[5] && !a[6]) break;solve();}return 0; }

大神的精辟解法：

#include<stdio.h> int main() {int n,a,b,c,d,e,f,x,y;int u[4]={0,5,3,1};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=d+e+f+(c+3)/4;y=5*d+u[c%4];//在已有n個(gè)的情況下，能裝下y個(gè)2*2的if(b>y)n+=(b-y+8)/9;//把多的2*2的弄進(jìn)來(lái)x=36*n-36*f-25*e-16*d-9*c-4*b;if(a>x)n+=(a-x+35)/36;//把1*1的弄進(jìn)來(lái)printf("%d\n",n);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/CSLaker/p/7295047.html

總結(jié)

以上是生活随笔為你收集整理的【贪心算法】POJ-1017的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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