Bin Packing

시간 제한4초메모리 제한256 MB

요약

무게가 각각 주어진 24개 이하의 물건을 용량 S인 통에 담을 때, 각 통의 합이 S를 넘지 않도록 하는 최소 통 개수를 구한다.

문제

무게가 $w\_1, w\_2, \ldots, w\_n$ 인 물건 $n$ 개가 주어진다. 각 상자에 담긴 물건의 무게 합이 $S$ 이하가 되도록 모든 물건을 상자에 담을 때, 필요한 상자의 최소 개수를 구한다.

첫째 줄에 정수 $n$ 과 $S$ 가 주어진다. $1 \leq n \leq 24$ 이고 $1 \leq S \leq 10^8$ 이다. 둘째 줄에 $w\_1, w\_2, \ldots, w\_n$ 이 주어진다. $1 \leq w\_i \leq S$ 이다.

주어진 물건을 모두 담는 데 필요한 상자의 최소 개수를 출력한다.

물건들은 크기 10인 상자 세 개에 다음과 같이 담을 수 있다: [5,3], [6], [7]. 전체 무게가 21이므로 두 상자에 담는 것은 불가능하다.