doodle
doodle

1017//装箱问题/贪心问题

描述一个工厂制造的产品形状都是长方体,它们的高度都是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
//较为容易..但细节容易出错
#include <iostream>
#include <cstring>
using namespace std;
int a[7];
int r[7];
int main()
{

while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6])
{
int num=0;
memset(r,0,sizeof(r));
if(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]==0)
break;
else{
if(a[6]!=0)
num+=a[6];
if(a[5]!=0){
num+=a[5];
r[1]=11*a[5];
}
if(a[4]!=0){
num+=a[4];
r[2]=5*a[4];
}
if(a[3]!=0){

num+=(a[3]+3)/4;
r[3]=((a[3]+3)/4)*4-a[3];
switch(r[3]){
case 1:
r[2]+=1;
r[1]+=5;
break;
case 2:
r[2]+=3;
r[1]+=6;
break;
case 3:
r[2]+=5;
r[1]+=21;
break;
default:
break;

}
}

if(r[1]>=a[1]){
if(r[2]>=a[2])
cout<<num<<endl;
else
{num+=(a[2]-r[2]+8)/9;
cout<<num<<endl;
}}
else {if(r[2]>=a[2]){
r[1]+=(r[2]-a[2])*4;
if(r[1]>=a[1])
cout<<num<<endl;
else{num+=(a[1]-r[1]+35)/36;
cout<<num<<endl;}

}
else
{
num+=(a[2]-r[2]+8)/9;
r[1]+=4*(((a[2]-r[2]+8)/9)*9-a[2]+r[2]);
if(r[1]>=a[1])
cout<<num<<endl;
else
{
num+=(a[1]-r[1]+35)/36;
cout<<num<<endl;
}
}

}

}
}

return 0;
}1017//装箱问题/贪心问题1017//装箱问题/贪心问题