탐욕 알고리즘 Problem R 1017 최소 필요 한 패키지 구하 기

Problem R  Problem ID:1017
간단 한 제목: 물품 은 모두 6 가지 규격 이 있 습 니 다. 1 * 1, 2 * 2, 3 * 3, 4 * 4, 5 * 5, 6 * 6. 그들 은 6 * 6 의 소포 에 넣 어 고객 에 게 보 낼 것 입 니 다.각 규격 의 물품 수량 을 이미 알 고 있 으 니, 최소 몇 개의 소포 가 필요 합 니까?
문제 풀이 사고의 형성 과정: 6 * 6 의 아 이 템 부터 아래로 옮 겨 다 니 며 더 큰 아 이 템 을 우선 놓 습 니 다.
① 각 6 * 6 의 아 이 템 은 각각 1 개의 소 포 를 차지한다.
② 5 * 5 의 물품 은 1 * 1 의 11 개 를 함께 보관 할 수 있다.
③ 4 * 4 아 이 템 은 2 * 2 아 이 템 5 개 를 함께 배치 할 수 있다.
④ 3 * 3 의 물건 은 3 * 3 의 물건 3 개 또는 2 * 2 + 7 개의 1 * 1 의 물건 5 개 를 함께 놓 을 수 있다.
⑤ 2 * 2 의 경우 2 * 2 의 물건 8 개 또는 1 * 1 의 물건 32 개 를 함께 놓 을 수 있다.
⑥ 한 소포 에 1 * 1 을 모두 넣 으 면 36 개 를 넣 을 수 있다.
(상기 과정 중 2 * 2 의 아 이 템 을 이미 다 놓 았 다 면 2 * 2 의 아 이 템 당 1 * 1 의 아 이 템 4 개 로 교환 가능)
소감: 디 테 일 에 주의 하 세 요.어디 가 잘못 되 었 는 지 모 르 겠 을 때 스스로 예 를 들 어 테스트 를 해 볼 수 있다.
코드:
#include<iostream>
#include<stdio.h>
using namespace std;
int a[6];
void de1(int n)
{
    if(a[0]<=n)
        a[0]=0;
    else
        a[0]-=n;
}

void de2(int n)
{
    if(a[1]>=n)
        a[1]-=n;
    else
    {
        int m=4*(n-a[1]);
        a[1]=0;
        de1(m);
    }
}

void de3(int n)
{
    if(a[2]>=n)
        a[2]-=n;
    else if(a[2]==0){
        de2(5);
        de1(7);
    }
    else if(a[2]==1){
        a[2]=0;
        de2(3);
        de1(6);
    }
    else if(a[2]==2){
        a[2]=0;
        de2(1);
        de1(5);
    }
}

int main()
{
    while(1){
        int cnt=0;
        scanf("%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5]);
        if((a[0]||a[1]||a[2]||a[3]||a[4]||a[5])==false)
            return 0;
        if(a[5]){
            cnt+=a[5];
            a[5]=0;
        }
        for(int i=4;i>=0;--i){
          if(i==4)
            while(a[i]){
            --a[i];
            de1(11);
            ++cnt;
            }
          else if(i==3)
            while(a[i]){
                --a[i];
                de2(5);
                ++cnt;
            }
          else if(i==2)
            while(a[i]){
                --a[i];
                de3(3);
                ++cnt;
            }
          else if(i==1)
            while(a[i]){
                --a[i];
                de2(8);
                ++cnt;
            }
          else if(i==0)
            while(a[i]){
                --a[i];
                de1(35);
                ++cnt;
            }
        }
        cout<<cnt<<endl;
    }
}

좋은 웹페이지 즐겨찾기