검색어 입력폼

Bin Packing 발표 자료

저작시기 2009.11 |등록일 2010.01.13 파워포인트파일MS 파워포인트 (pptx) | 61페이지 | 가격 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.
다운로드 맨위로