贪心法(三):POJ题库中的贪心法应用例题
下面我们通过解决POJ题库中的几道应用贪心法思想编写程序的例题,进一步体会贪心法的应用。
【例1】产品包装。
问题描述
某工厂生产的产品高度均为h,截面尺寸分为1*1、2*2、3*3、4*4、5*5、6*6。工厂收到客户订单后,将订单中的产品用与产品高度h相同,尺寸为6*6的包装盒包装后寄给客户。
问最少要多少个包装盒?
输入
输入每行指定一个订单。每个订单由六个整数描述,由一个空格分隔,依次表示从最小大小1*1到最大大小6*6的各个规格的产品的数量。输入的结尾由包含六个零的行表示。
输出
输出文件为输入文件中的每一行包含一行。此行包含可将输入文件对应行中的订单打包到其中的最小数量的包装盒数。
输入样例
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
输出样例
(1)编程思路。
贪心策略是优先从最大规格的产品需要的包装盒数来考虑,因为一个包装盒在装完较大规格的产品后,该包装盒可能存在剩余空间,仍应该利用。
显然,6*6、5*5、4*4规格的每一个产品都需要一个包装盒,3*3规格的产品每四个装满一个包装盒,然后将剩余2*2和1*1规格的产品依次放入之前包装盒的空余部分。
6*6规格的产品需要一个包装盒且空间全占满,无剩余;5*5规格的产品需要一个包装盒,该包装盒还可以装11个1*1规格的产品;4*4规格的产品需要一个包装盒,该包装盒还可以最多装5个2*2规格或20个1*1规格的产品。但该包装盒剩余空间应优先考虑装2*2规格的产品。
对于3*3规格的产品,一个包装盒可以装1到4个3*3规格的产品,剩下的空间同样优先考虑装2*2规格的产品。简单在纸上画一下可得知,一个包装盒分别装1、2、3、4个3*3规格的产品后,剩余空间最多可以装5、3、1、0个2*2规格的产品。
剩下的2*2规格和1*1规格的产品就首先放进前面各较大规格产品所装包装盒剩余的空间中,不够的话启用新包装盒。
(2)源程序。
#include
int main()
{
while (1)
{
int b1,b2,b3,b4,b5,b6;
scanf("%d%d%d%d%d%d",&b1,&b2,&b3,&b4,&b5,&b6);
if (b1+b2+b3+b4+b5+b6==0) break;
int ans,x1,x2;
ans=b6+b5+b4+(b3+3)/4;
x2=b4*5; // 装一个规格4产品的箱子还可装5个规格2的产品
switch (b3%4)
{
case 1: x2+=5; break;
case 2: x2+=3; break;
case 3: x2++;
}
if (x2 ans=ans+(b2-x2+8)/9; x1=36*ans-36*b6-25*b5-16*b4-9*b3-4*b2; if (x1 ans=ans+(b1-x1+35)/36; printf("%d\n",ans); } return 0; } 注:将此源程序提交给POJ 1017 Packets(http://poj.org/problem?id=1017)可以Accepted。 【例2】1的个数相同。 问题描述 给定一个大于0的整数n,把它转换为二进制,则其二进制数中至少有1位是“1”。编写一个程序,找出比给定的整数n大的最小整数m。要求m和n两个整数转换成二进制数后,二进制数中包含的1的个数相同。 例如,120的二进制数为01111000,则比120大且二进制数中1的个数相同的最小整数为135(10000111)。 输入 每行一个整数n(1 <= n<= 1000000),n=0表示输入结束。 输出 每行一个整数,为比n大的最小整数m,且m、n所对应的二进制数中1的个数相同。 输入样例 78 输出样例 83 (1)编程思路。 对十进制数n转化成的二进制数直接进行位变换,求出最小的整数m。 贪心方法是:先找到整数n对应的二进制数的最右边的1个1,从这个1开始,从右向左将连续出现的k个1变为0后,高1位的0变为1,再从最低位开始,将k-1个0变为1,即可得到最小的数n。 例如,32 对应的二进制数为00100000,将最右边的连续1个1变为0,高1位0变为1,即为01000000,对应整数为64。 又如,92 对应的二进制数为 01011100,将最右边的连续3个1变为0(得01000000),高1位变为1(得01100000),再将最低位的2(3-1)个0变为1,即为01100011,对应整数为99。 (2)源程序。 #include int main() { int n; while (scanf("%d",&n) && n!=0) { int a,b,k,m;