A36049. 装箱问题
填空题
较难
知识点
题目描述
装箱问题
题目描述
一个工厂制造的产品形状都是长方体，它们的高度都是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：贪心
#include <bits/stdc++.h>
using namespace std;
int status[8][4];//status[i][j]:包裹中已有1个大小为i*i的产品，此时可以最多放入多少个j*j的产品
void initStatus()
{//status[0]:包裹中没有产品时，各种产品最多可以放多少个
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产品的数量
int main()
{
initStatus();
while(true)
{
int sum = 0, bag = 0, rem[8];//sum:总产品数量 bag:包裹数 rem[i]:当前剩余空间能放几个i*i
for(int i = 1; i <= 6; ++i)
{
cin >> pro[i];
sum += pro[i];
}
if(sum == 0)//如果6个数都是0，那么加和为0，要跳出循环
break;
for(int i = 6; i >= 1; --i)
{
while(pro[i] > 0)
{
bag++;//用一个新包裹放i*i
pro[i]--;
for(int j = 1; j <= 3; ++j)//获取当前剩余空间情况
rem[j] = status[i][j];
int j = 3;
while(j >= 1)
{
if(rem[j] > 0 && pro[j] > 0)//如果可以放j*j的产品
{
pro[j]--;//放一个产品
if(j == 3)
{
rem[3]--;
rem[2] -= 2;
rem[1] -= 9;
}
else if(j == 2)
{
rem[2]--;
rem[1] -= 4;
}
else//j == 1
rem[1]--;
}
else
--j;
}
}
}
cout << bag << endl;
}
return 0;
}
上一题
下一题