Bin-packing 문제란?


같은 크기의 상자들이 있다. 편의상 크기를 1이라고 하자.
거기에 집어넣어야 하는 물건들이 있다. 이들의 크기는 다를 수도 있고, 아무튼 1을 넘지는 않는다.


그러면 어떻게 집어넣어야 상자를 최소한으로 쓰고 넣을 수 있는가 하는문제임


일단 Subset sum에서 Reduction을 이용해서 동일한 난이도임을 보일 수 있어서 NPC임.


그래서 TSP 마냥 Approx 알고리즘을 연구하기 시작함.
가장 먼저 나온게 First Fit Decreasing임 (엄밀하게는 Non-increasing 이지만)


알고리즘은 간단함.


1. 물건을 크기가 줄어드는 순서로 정렬함
2. 1번 상자부터 물건을 집어넣으려고 시도함. 되면 넣고 아니면 다음 상자로
3. 상자가 더 필요하면 가져옴


이 때, 최적으로 넣었을 때 필요한 상자의 수가 OPT라고 하면, OPT 다음번의 상자부터는 Extra bins라고 함.
우리가 보여야 할 문제는 Extra bins에 들어가 있는 각각의 물건들의 크기가 1/3보다 작거나 같다는 거임.


만약 어떤 물건이 1/3 보다 큰데 Extra bins에 들어갔다고 해보자. (i번째라고 하자)
그러면 우리가 크기가 줄어드는 순서대로 정렬을 했으니, 그 물건 앞의 물건들은 모두 1/3보다 클거임
그러면 앞의 상자에는 아무리 많이 넣어보았자 2개 이상은 집어넣을 수가 없음.


그런데 넣는 방식을 잘 생각해보면, 맨 처음 상자에서 특정 상자까지는 1개씩만 들어가고
그 다음 상자부터는 2개씩 집어넣어져 있을 거임.


그러면 1개씩만 들어간 물건들은, i번째 까지 넣었을 때 다른 얘들과 같이 들어갈 수 없다는 뜻임.
이 때, i번째 물건까지 넣어서 optimal solution을 생각해보면,


(1) 이는 물건의 개수가 줄었으므로 원래의 OPT보다 적거나 같은 수의 상자를 사용해야 함
(2) 그런데 앞의 1개씩만 들어간 물건들은 다른 물건과 같이 넣을 수 없음
(3) 그리고 남은 자리에는 1/3보다 크기 때문에 많아야 2개씩만 넣을 수 있음


잘 생각해보면 FFD와 크게 다를바가 없는 것을 알 수 있고, i번째 물건은 들어갈 자리가 없어짐
따라서 이건 모순이고, Extra bins에 들어간 물건의 크기는 1/3보다 작거나 같아야 함.