탐욕 알고리즘 Problem R 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;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.