Bin Packing 발표 자료
- 최초 등록일
- 2010.01.13
- 최종 저작일
- 2009.11
- 61페이지/
MS 파워포인트
- 가격 1,000원
소개글
알고리즘 수업에서 Bin Packing에 대한 발표 시 사용한 ppt 자료 입니다.
Bin Packing의 정의, NP-Completeness 증명, Approximation Algorithms(근사 알고리즘들)에 대한 내용으로 구성되어 있습니다.
목차
Introduction
Problem definition
NP-complete proof
Exact solution
Approximation algorithms
Summary
본문내용
- 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
Input:
n items with sizes
s1, ... , sn
where 0 < si ≤ 1 for 1 ≤ i ≤ n.
Output:
Pack items into a minimum number of unit-capacity bins.
Sample:
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.
참고 자료
없음
