简答题
偏难
#7430
装箱问题 一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6…
装箱问题
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
时间限制:1000
内存限制:65536
输入
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法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;
}</pre><pre class="brush:cpp;toolbar:false">//解法2:手动完成贪心过程
#include<bits/stdc++.h>
using namespace std;
int bag;//总包裹数
int k[4] = {0, 5, 3, 1};//k[i]表示3*3的产品有i个时(k[0]表示有4个时)剩余空间可以放2*2产品的个数
int pro[8], p2, p1;//p2:2*2空位数 p1:1*1空位数
int main()
{
while(true)
{
for(int i = 1; i <= 6; ++i)
cin >> pro[i];
if(pro[1] == 0 && pro[2] == 0 && pro[3] == 0 && pro[4] == 0 && pro[5] == 0 && pro[6] == 0)
break;
bag = pro[6] + pro[5] + pro[4] + ceil(pro[3]/4.0);//6*6和5*5和4*4一定是一个占一个箱子,而3*3 4个占一个箱子
p2 = 5*pro[4]+k[pro[3]%4];//k[pro[3]%4]:有pro[3]%4个3*3在一个包裹中时,剩下的位置可以放2*2的数目
if(pro[2] > p2)//2*2的个数比我们留出来为2*2的空间个数多,就需要为2*2另开箱子
bag += ceil((pro[2]-p2)/9.0);//多出来的2*2箱子应该占用的新箱子数
p1 = 36*bag-36*pro[6]-25*pro[5]-16*pro[4]-9*pro[3]-4*pro[2];//求出当前包裹中所有剩下的可以放1*1的位置数
if(pro[1] > p1)//如果1*1的个数,比我们留出的空间多就需要另开空间
bag += ceil((pro[1]-p1)/36.0);//将多出来的另开箱子
cout << bag << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 101
using namespace std;
int main()
{
int a,b,c,d,e,f;
int g[4]={0,5,3,1};
int x,y;
while(cin>>a>>b>>c>>d>>e>>f)
{
if(a+b+c+d+e+f==0)
break;
int n=f+e+d+(c+3)/4;
x=5*d+g[c%4];
if(b>x)
n+=(b-x+8)/9;
y=36*n-36*f-25*e-16*d-9*c-4*b;
if(a>y)
n+=(a-y+35)/36;
cout<<n<<endl;
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。