packing 문제의 목표는 지정된 크기의 항목 세트를 고정된 packing이 있는 컨테이너에 패킹하는 가장 좋은 방법을 찾는 것입니다. 일반적인 애플리케이션은 배송 트럭에 상자를 효율적으로 적재하는 것입니다. 용량 제약으로 인해 모든 항목을 담을 수 없는 경우가 많습니다. 이 경우 문제는 컨테이너에 맞는 최대 총 크기가 있는 항목의 하위 집합을 찾는 것입니다.
포장 문제에는 여러 유형이 있습니다. 가장 중요한 두 가지는 배낭 문제와 빈 패킹입니다.
배낭 문제
간단한 배낭 문제에는 1개의 컨테이너 (배낭)가 있습니다. 항목에는 값과 크기가 있으며 총가치가 가장 큰 항목의 하위 집합을 패킹하는 것이 목표입니다.
값이 크기와 같은 특수한 경우 목표는 압축된 항목의 총 크기를 극대화하는 것입니다.
OR-Tools는 알고리즘 라이브러리에서 배낭 문제의 여러 해결자를 제공합니다.
배낭 문제의 보다 일반적인 버전도 있습니다. 다음은 몇 가지 예입니다.
다차원 배낭 문제: 물건에 무게와 부피와 같이 물리적 수량이 두 개 이상 있으며 배낭에 각 수량을 담을 수 있는 용량이 있습니다. 여기서 크기라는 용어는 높이, 길이, 너비의 일반적인 공간 크기를 반드시 지칭하지는 않습니다. 그러나 직사각형 상자를 직사각형 저장소에 넣는 최적의 방법을 찾는 것과 같은 문제에는 공간적 차원이 포함될 수 있습니다.
여러 배낭 문제: 배낭이 여러 개 있으며 모든 배낭에 들어 있는 물품의 총 가치를 극대화하는 것이 목표입니다.
단 하나의 배낭에는 다차원 문제가 있을 수도 있고, 차원이 하나인 여러 개의 배낭 문제가 있을 수도 있습니다.
빈 패킹 문제는
가장 잘 알려진 패킹 문제 중 하나는 용량이 같은 여러 개의 컨테이너 (bin-packing이라고 함)가 있는 bin-packing입니다. 여러 개의 배낭 문제와 달리 상자 수는 고정되지 않습니다. 대신 모든 항목을 포함할 가장 적은 수의 구간을 찾는 것이 목표입니다.
다음은 다중 배낭 문제와 빈 패킹 문제의 차이를 보여주는 간단한 예입니다. 회사에 18,000파운드의 중량과 130,000파운드의 물품을 배송할 수 있는 배송 트럭이 있다고 가정해 보겠습니다.
여러 배낭: 5대의 트럭이 있고 중량이 최대인 물품의 일부를 트럭에 적재하려고 합니다.
쓰레기 적재: 20대의 트럭 (모든 물품을 담기에 충분할 정도로 많음)이 있으며 모든 물품을 담을 수 있는 가장 적은 수의 트럭을 사용하려 합니다.
다음 섹션에서는 knapsack 문제부터 시작하여 OR-Tools를 사용하여 다양한 유형의 패킹 문제를 해결하는 방법을 보여줍니다.