형식 문제
가변 크기 빈 패킹 (Variable-Sized Bin Packing)
여러 크기·비용의 빈이 주어질 때 총 빈 비용을 최소화하도록 담기.
다른 이름: Variable-Sized Bin Packing · Variable Sized Bin Packing Problem · VSBPP · 가변 크기 빈 패킹
마지막 검증: 2026-05-27
정의
서로 다른 크기와 비용의 빈 종류가 주어졌을 때, 모든 항목을 겹치지 않게 담되 사용한 빈의 총 비용(또는 총 면적)을 최소화하도록 빈을 고르고 채운다. 표준 빈 패킹이 동일한 빈의 개수 를 줄이는 문제라면, 여기서는 어떤 크기의 빈을 쓸지 까지 고른다.
예시
빈 종류가 둘이라 하자 — A: 용량 10·비용 10, B: 용량 6·비용 7. 무게 합이 14인 항목 집합을 담을 때, A 하나로는 부족하다. A 하나 + B 하나(용량 16, 비용 17)면 충분하고, A 둘(비용 20)보다 싸다. 빈 개수 가 아니라 비용 을 최소화하므로, 큰 빈만 쌓는 것이 늘 최선은 아니다.
계열
2D 빈 패킹의 비용 가중 변형이며, 여러 재고 종류를 고르는 구조 때문에 1D 절단 재고와도 방법론적으로 닿는다.
관련 노드
아래 깊이 1 그래프를 참고하라.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 변형 관계2D 빈 패킹 | 가변 크기 빈 패킹은 빈이 여러 크기·비용으로 주어지는 빈 패킹 변형으로, 빈 개수가 아니라 총 빈 비용을 최소화한다 — Wäscher 외 유형론의 '빈 구색' 차원에서 갈린다. | E1 | A |
|
| 방법 공유1D 절단 재고 | 가변 크기 빈 패킹과 1D 절단 재고는 '여러 종류의 재고/빈을 비용 최소로 고른다'는 구조를 공유하며, 둘 다 패턴/구성 정식화로 다뤄진다. | E3 | B |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
그래프 불러오는 중…