알고리즘 수업에서 Bin Packing에 대한 발표 시 사용한 ppt 자료 입니다.
Bin Packing의 정의, NP-Completeness 증명, Approximation Algorithms(근사 알고리즘들)에 대한 내용으로 구성되어 있습니다.
- A Problem
We have n items each of size between 0 and 1
We want to pack these items into bins of size 1
We want to use the least possible number of bins
n items with sizes
s1, ... , sn
where 0 < si ≤ 1 for 1 ≤ i ≤ n.
Pack items into a minimum number of unit-capacity bins.
9 items with sizes 0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6
- Only known algorithm
to find optimal solution requires trying all possibilities of loading items
All cases that all items can be listed is n!
Thus, time complexity is O(n!)
Assign an arriving item to the same bin as the preceding item. If it does not fit, close it and open a new bin, place it there, set the new bin as the last used bin for next item
Assign an arriving item to the first bin (i.e. that was opened earliest) in which it fits. If there is no such bin, open a new one and place it there.