Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

裸的贪心,汗啊汗

Posted by wrong123 at 2005-12-06 01:29:01 on Problem 1017
//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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator