1D 절단 재고

정의

고정 길이의 재고와, 필요한 더 짧은 길이별 수요가 주어졌을 때, 최소 개수의 재고로 수요를 충족하도록(즉 트림 손실 최소화) 절단 패턴을 선택한다.

예시

재고 길이 $L = 10$, 수요가 길이 6짜리 3개와 길이 4짜리 5개라고 하자. 패턴 “6+4”(길이 합 $6+4=10$, 트림 0)를 세 번 쓰면 6짜리 3개와 4짜리 3개가 나오고, 남은 4짜리 2개는 패턴 “4+4”(길이 8, 트림 2) 한 번으로 충당한다. 합계 재고 4개, 총 트림 손실 2 — 6짜리는 한 재고에 하나뿐이라 최소 3개가 필요하고 남은 4짜리에 1개가 더 들기 때문에 이보다 적게는 불가능하다.

여기서 중요한 이유

이 문제는 열 생성의 본고장이다: 모든 절단 패턴을 열거하는 대신, Gilmore–Gomory 접근은 배낭 가격 산정 부분문제를 풀어 유망한 패턴을 필요할 때 생성한다. 같은 기법이 절단·적재 계열 전반에 다시 등장한다.

관련 노드

아래 깊이 1 그래프를 참고하라.