| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
裸的贪心,汗啊汗//Problem: Poj 1017 --装盒子问题 贪婪求解,从最大的开始装起,剩余容量的选择也是从最大可容纳的中选
#include<iostream>
using namespace std;
int A[7];
int main()
{
int i,j,count,left;
while(true)
{
count=0; left=0; //count记录需要的箱子数,left记录每次装一批A[i]后剩余的容量
for(i=1;i<=6;i++)
cin>>A[i];
if(A[1]==0&&A[2]==0&&A[3]==0&&A[4]==0&&A[5]==0&&A[6]==0) break;
count=A[6];
if(A[5]) //订有5*5的产品
{
count += A[5];
left=11*A[5];
if(left>=A[1])A[1]=0; //装了5*5的产品后的盒子空余空间可以全部容纳要求的1*1
else {A[1] -= left; left=0;}
}
if(A[4]) //订有4*4的产品
{
count += A[4];
left=20*A[4];
if(left>=4*A[2]) //剩余空间可以装下所有2*2
{
left -= 4*A[2]; A[2]=0;
if(left>=A[1])A[1]=0;
else {A[1] -= left; left=0;}
}
else A[2] -= left/4; //否则装不了所有2*2,则更新A[2]
}
if(A[3])
{
if(A[3]%4==0) { count += A[3]/4; left = 0;} //刚好所有的A[3]可以装 A[3]/4个袋子
else //否则进入一下分析
{
count += A[3]/4+1;
left = (4-A[3]%4)*9;
if(A[2]<=2*(4-A[3]%4)-1) //2*(4-A[3]%4)-1为最多可放置的2*2数
{
left -= A[2]*4; A[2]=0;
if(left>=A[1])A[1]=0;
else {A[1] -= left; left=0;}
}
else
{
left -= 4*(2*(4-A[3]%4)-1); A[2] -= 2*(4-A[3]%4)-1;
if(left>=A[1])A[1]=0;
else {A[1] -= left; left=0;}
}
}
}
if(A[2])
{
if(A[2]%9==0){ count += A[2]/9; left = 0;}
else
{
count += A[2]/9+1;
left = 36-4*(A[2]%9);
if(left>=A[1])A[1]=0;
else {A[1] -= left; left=0;}
}
}
if(A[1])
{
if(A[1]%36==0)count += A[1]/36;
else count += A[1]/36+1;
}
cout<<count<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator