빈 패킹(상자 채우기) 근사 계산기
크기가 다른 짐을 같은 용량의 상자에 최소 개수로 나눠 담습니다. NF·FF·FFD·BFD 네 가지 근사법을 나란히 돌리고, 「이보다 적을 수는 없다」는 하한과 함께 보여 줍니다.
쉼표나 공백으로 구분합니다. 200개까지.
「FFD 한계 반례」 예시를 고르면 용량을 1000으로 맞춰 주세요.
짐 12개 · 용량 20
5상자
하한 5상자와 같으므로 이것이 최적해입니다. 이보다 적게 담는 방법은 원리적으로 없습니다.
방법별 상자 수
| 방법 | 상자 | 평균 채움 | 버린 자리 |
|---|---|---|---|
| NF — 다음 맞춤 | 6 | 76.7% | 28 |
| FF — 첫 맞춤 | 5 | 92% | 8 |
| FFD — 큰 것부터 첫 맞춤 | 5 | 92% | 8 |
| BFD — 큰 것부터 최적 맞춤 | 5 | 92% | 8 |
- NF — 다음 맞춤 — 지금 상자에 안 들어가면 바로 새 상자를 엽니다. 앞 상자는 다시 보지 않아 자리가 남아도 못 씁니다.
- FF — 첫 맞춤 — 열린 상자를 앞에서부터 훑어 처음 들어가는 곳에 넣습니다.
- FFD — 큰 것부터 첫 맞춤 — 큰 짐을 먼저 자리 잡게 하고 작은 짐으로 틈을 메웁니다. 실무에서 가장 많이 씁니다.
- BFD — 큰 것부터 최적 맞춤 — 큰 것부터, 넣었을 때 남는 자리가 가장 적은 상자를 고릅니다.
FF — 첫 맞춤으로 담은 결과
12 · 7
9 · 3 · 6 · 2
15 · 4
8 · 11
5 · 10
계산 방법
- 1짐 크기를 쉼표나 공백으로 구분해 넣습니다.
- 2상자 용량을 정합니다. 용량보다 큰 짐이 있으면 담을 수 없습니다.
- 3방법별 상자 수를 비교하고, 하한과 같은지 확인합니다.
- 4가장 좋은 방법으로 담은 결과에서 상자마다 무엇이 들어갔는지 봅니다.
자주 묻는 질문
빈 패킹이 NP-난해 문제이기 때문입니다. 짐이 스무 개만 되어도 모든 배치를 훑는 것은 현실적이지 않아, 실무에서는 근사법을 쓰고 하한과 견주는 방식으로 「충분히 좋은지」를 판단합니다.
짐의 총합을 상자 용량으로 나눈 뒤 올림합니다. 상자를 아무리 잘 채워도 총합보다 많이 담을 수는 없기 때문에 그보다 적은 상자는 원리적으로 불가능합니다. 근사 결과가 하한과 같으면 그것이 곧 최적해라는 증명이 됩니다.
큰 짐을 먼저 자리 잡게 하면 남는 틈을 작은 짐으로 메울 수 있기 때문입니다. 작은 짐을 먼저 흩뿌리면 나중에 큰 짐이 들어갈 자리가 없어 새 상자를 계속 열게 됩니다. 그래서 FFD가 FF보다 대체로 낫습니다.
최적해 OPT에 대해 (11/9)·OPT + 6/9 이내가 보장됩니다(Dósa, 2007). 최적이 9상자면 FFD는 최대 11상자라는 뜻이고, 이 한계가 실제로 붙는 예가 존재합니다. 이 계산기의 「FFD 한계 반례」 예시를 용량 1000으로 돌려 보면 확인할 수 있습니다.
앞서 연 상자를 다시 보지 않기 때문입니다. 지금 상자에 안 들어가면 바로 새 상자를 열고, 앞 상자에 자리가 남아 있어도 쓰지 않습니다. 대신 짐이 순서대로 흘러 들어오는 상황(컨베이어 위)에서는 앞을 되짚을 수 없어 이 방식밖에 쓸 수 없습니다.
목적이 다릅니다. 배낭 문제는 가방 하나에 가치가 최대가 되게 담는 것이고, 빈 패킹은 모든 짐을 담되 상자 개수를 최소로 하는 것입니다. 빈 패킹에는 버리는 짐이 없습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 작은 판에서 최적 상자 수를 전수 탐색으로 구해 대조했습니다. 무작위 60벌에서 네 근사법이 모두 최적보다 적지 않은 것과, FFD가 대부분 최적을 맞히는 것을 확인했습니다.
- FFD의 11/9 한계가 실제로 붙는 예를 테스트로 고정했습니다. 용량 1000에 501×6, 252×6, 251×6, 248×12를 넣으면 하한이자 최적이 9상자인데 FFD는 11상자를 씁니다. 501+251+248 = 1000과 252+252+248+248 = 1000이라 9상자 배치가 실제로 존재합니다.
- 담은 결과가 성립하는지 매번 검사합니다. 무작위 100벌에서 짐이 빠짐없이 한 번씩만 담겼는지, 어느 상자도 용량을 넘지 않았는지, 결과가 하한 이상인지 확인했습니다.
- 정렬이 이롭다는 것도 무작위 100벌에서 확인했습니다(FFD가 FF보다 적거나 같은 경우가 90벌 이상).
- 짐은 200개까지 다룹니다. 크기는 정수가 아니어도 되지만 소수를 넣으면 표시 자릿수 안에서 반올림되어 보입니다.
- 한 종류 용량의 상자만 다룹니다. 크기가 여러 가지인 상자, 무게와 부피를 함께 보는 문제, 2차원·3차원 적재는 다루지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.