- 넣는 중인 물건
- 들어감
- 안 들어감
빈 패킹 문제
상자는 밴에, 파일은 디스크에, 작업은 기계에. 빈 패킹 문제는 물건 목록을 같은 크기의 빈에 되도록 적게 넣는 방법을 묻습니다. 항상 최선의 채우기를 찾는 빠른 방법은 알려져 있지 않지만, 간단한 규칙으로도 꽤 가까워집니다. 규칙을 고르고 단계별로 진행한 다음 정확한 답과 비교해 보세요. 선반의 물건을 탭한 다음, 넣을 빈을 탭하세요. 초록색 빈에는 그 물건이 들어갈 자리가 있고, 새 빈 버튼은 빈을 하나 더 엽니다. 빈 안의 물건을 탭하면 다시 꺼낼 수 있습니다. 모든 물건을 되도록 적은 빈에 넣으세요. 하한(총 무게를 빈 크기로 나눈 뒤 올림한 값)과 가능한 최소를 보면 얼마나 가까운지 알 수 있고, 최소 빈 버튼은 가장 좋은 패킹을 보여 줍니다. 패널에서 물건의 무게(킬로그램 단위)와 빈 크기를 바꿀 수 있습니다. 단계별 보기에서는 빠른 규칙이 어떻게 넣는지 보여 줍니다. 다음 적합, 최초 적합, 최적 적합을 입력한 순서 그대로 또는 큰 것부터 정렬한 물건에 적용하거나, 동적 계획법으로 구한 정확한 답을 볼 수 있습니다. 재생을 누르면 물건이 빈에 들어가는 모습을 볼 수 있고, 단계와 뒤로를 누르면 한 단계씩 움직이며, 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 움직이고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 물건을 누른 다음 공간이 있는 빈을 눌러 넣거나, 새 빈 버튼을 눌러 빈을 하나 더 여세요.
- 가능한 한 적은 빈을 써 보거나, 최소 빈 버튼을 눌러 가장 좋은 배치를 확인하세요.
- 단계별 보기를 열고 규칙을 고른 뒤 재생을 눌러 각 물건이 빈을 차례로 시도하는 과정을 지켜보세요.
규칙
다음 적합은 마지막 빈만 열어 둡니다. 거기에 들어가지 않는 물건은 새 빈을 시작합니다. 최초 적합은 첫 번째 빈부터 시도해 자리가 있는 첫 번째 빈을 고릅니다. 최적 적합은 모든 빈을 시도해 자리가 있는 빈 중 가장 꽉 찬 빈을 골라 남는 공간을 가장 적게 만듭니다. 최초 적합과 최적 적합은 물건을 먼저 큰 것부터 작은 것 순으로 정렬할 수도 있는데, 이것이 내림차순 최초 적합과 내림차순 최적 적합입니다.
정확한 답
마지막 규칙은 경험 규칙이 아닙니다. 물건 집합에 대한 동적 계획법으로 최소 빈 개수를 찾습니다. 물건의 모든 집합마다 그 물건들을 담는 최소 빈 개수와, 그 개수의 빈을 쓰는 채우기 중 마지막 빈의 가장 작은 적재량을 기록합니다. 집합은 물건을 하나씩 더하며 커지고, 더해진 물건은 마지막 빈에 들어가거나 새 빈을 엽니다. 물건이 n개면 집합은 2ⁿ개이므로 이 앱에서는 물건을 최대 12개까지만 쓸 수 있습니다. 하한, 즉 총 크기를 빈 크기로 나누어 올림한 값은 채우기가 최선에 얼마나 가까운지 보여 줍니다.
자주 묻는 질문
어떤 빈 패킹 규칙이 가장 좋나요?
빠른 규칙 중에서는 내림차순 최초 적합과 내림차순 최적 적합이 가장 강력합니다. 최소 빈 개수의 11/9에 작은 상수를 더한 것보다 많은 빈을 절대 쓰지 않습니다. 정렬하지 않은 물건에 대한 최초 적합과 최적 적합은 최소 빈 개수의 1.7배 이내, 다음 적합은 2배 이내입니다.
빈 패킹은 왜 어렵나요?
물건이 빈 두 개에 들어가는지 판단하는 것만으로도 이미 분할 문제이며, 이는 NP-완전입니다. 따라서 P = NP가 아니라면 모든 입력에 대해 최소 빈 개수를 빠르게 찾는 방법은 없고, 정확한 방법은 최악의 경우 지수 시간이 걸립니다.
하한이란 무엇인가요?
물건의 총 크기를 빈 크기로 나누어 올림한 값입니다. 빈에 모든 물건이 들어가야 하므로 어떤 채우기도 이보다 적은 빈을 쓸 수 없습니다. 최선의 채우기가 하한과 같은 경우가 많지만 항상 그렇지는 않습니다. 크기 6인 물건 세 개와 크기 10인 빈은 하한이 2이지만 빈이 3개 필요합니다.
이것이 동적 계획법인가요?
정확한 답은 그렇습니다. 모든 물건 집합에 대한 최선의 채우기를 더 작은 집합의 최선의 채우기로부터 만듭니다. 빠른 규칙은 탐욕 알고리즘으로, 한 번 결정하면 다시 돌아보지 않습니다.
어딘가로 전송되는 것이 있나요?
아니요. 모든 계산은 브라우저에서 이루어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동