빈 패킹 문제
이사할 때 상자를 하나씩 채우다 보면, 더 영리한 순서였다면 상자가 덜 들었을까 궁금해집니다. 그것이 바로 빈 패킹 문제이고, 어렵기로 유명합니다. 컴퓨터조차 큰 입력에서는 영리한 탐색을 통해서만 최소 빈 개수를 찾습니다. 하지만 간단한 규칙도 놀라울 만큼 가까워집니다.
문제
크기가 있는 물건들과 모두 같은 양을 담는 빈들이 주어질 때, 어떤 빈도 넘치지 않게 모든 물건을 빈에 넣되 빈을 되도록 적게 쓰는 문제입니다. 크기는 무게, 길이, 시간, 파일 크기를 나타낼 수 있습니다. 비 오는 오후의 퍼즐처럼 들리지만 NP-난해입니다. 모든 입력에 대해 최소 빈 개수를 빠르게 찾는 방법은 알려져 있지 않습니다.
빠른 규칙
다음 적합은 다음 물건이 들어가지 않을 때까지 한 빈을 채운 뒤 새 빈을 시작하고 다시는 돌아보지 않습니다. 최초 적합은 모든 빈을 열어 두고 각 물건을 자리가 있는 첫 번째 빈에 넣습니다. 최적 적합은 각 물건을 아직 자리가 있는 가장 꽉 찬 빈에 넣습니다. 세 규칙 모두 즉시 결정하므로, 물건이 하나씩 도착해 바로 배치해야 할 때 유용합니다.
먼저 정렬하기
어려운 것은 큰 물건입니다. 빈 공간이 많이 필요하기 때문입니다. 물건을 큰 것부터 작은 것 순으로 정렬한 뒤 최초 적합이나 최적 적합을 쓰면, 빈이 아직 비어 있을 때 큰 물건이 들어가고 작은 물건이 틈을 메웁니다. 내림차순 최초 적합은 최소 빈 개수의 11/9에 상수를 더한 것보다 많은 빈을 절대 쓰지 않으며, 정렬하지 않은 물건에 대한 최초 적합은 1.7배입니다.
예시
크기 10인 빈과 합이 40인 물건 2, 3, 2, 1, 3, 4, 5, 6, 7, 7을 생각해 봅시다. 최초 적합은 2, 3, 2, 1을 첫 번째 빈에, 3과 4를 두 번째 빈에 넣고, 그다음 5, 6, 7, 7은 각각 자기 빈이 필요합니다. 빈 6개입니다. 큰 것부터 정렬하면 내림차순 최초 적합은 7 + 3, 7 + 3, 6 + 4, 5 + 2 + 2 + 1을 만듭니다. 가득 찬 빈 4개로, 하한 40 / 10 = 4와 같습니다.
최소 빈 개수 찾기
물건이 적으면 부분집합에 대한 동적 계획법으로 정확한 답을 찾을 수 있습니다. 각 물건 집합에 대해, 그것을 담는 최소 빈 개수와 가장 비어 있는 마지막 빈을 물건이 하나 적은 집합들로부터 쌓아 올립니다. 물건이 n개면 약 2ⁿ·n 단계가 걸립니다. 더 큰 문제는 분기 한정법이나 정수 계획법으로 풀며, 하한은 채우기가 최선에서 얼마나 멀 수 있는지 알려 줍니다.
어디에 쓰일까
트럭과 컨테이너에 짐 싣기, 표준 길이의 파이프나 종이 롤을 낭비를 최소로 하며 자르기(절단 재고 문제), 가상 머신을 서버에 배치하기, 파일을 디스크에 담기는 모두 빈 패킹 문제입니다. 숫자 대신 상자를 쓰는 2차원과 3차원에서는 문제가 더욱 어렵습니다.
자주 묻는 질문
온라인 빈 패킹과 오프라인 빈 패킹은 무엇이 다른가요?
온라인에서는 나머지를 모르는 채로 각 물건이 도착하자마자 배치해야 합니다. 다음 적합, 최초 적합, 최적 적합이 이렇게 작동합니다. 오프라인에서는 모든 물건을 미리 알기 때문에, 내림차순 최초 적합처럼 먼저 정렬할 수 있습니다.
내림차순 최초 적합은 최적에 얼마나 가까운가요?
최소 빈 개수의 11/9에 빈 6/9개를 더한 만큼까지만 쓰며, 이 한계가 정확하다는 것을 2007년 György Dósa가 증명했습니다. 일반적인 입력에서는 대개 최적이거나 빈 하나 차이입니다.
빈 패킹은 배낭 문제와 같은가요?
관련은 있지만 다릅니다. 배낭 문제는 가방 하나를 가장 가치 있는 물건으로 채우고, 빈 패킹은 모든 물건을 되도록 적은 가방에 넣습니다. 정확한 빈 패킹 솔버는 배낭 문제와 비슷한 문제를 반복해서 풀며 작동하는 경우가 많습니다.
앱에서 물건을 12개까지만 쓸 수 있는 이유는 무엇인가요?
정확한 답이 물건의 모든 집합을 살펴보는데, 물건 12개만으로도 집합이 4,096개가 되기 때문입니다. 빠른 규칙은 수천 개의 물건도 처리할 수 있지만, 그림과 정확한 답과의 비교는 그렇지 못합니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
빈 패킹 해 보기