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