그리디 알고리즘

1.부분 배낭(Knapsack)문제

1.배낭(Knapsack)문제

*n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때,

최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제 

2.부분 배낭(Fractional Knapsack)문제 

*원래 배낭 문제는 물건을 통째로 배낭에 넣어야 되지만, 부분 배낭 문제는 문건을 부분적으로 담는 것을 허용함 

-단위 무게 강 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값 나가는 물건을 넣음

-만일 그다음으로 값나가는 문건을 통째로 배낭에 넣을 수 없게 되면 부분적으로 배낭에 담음

예제 문제 

시간 복잡도 O(nlogn)

2.집합 커버(Cover)문제 

 n개의 원소를 가진 집합인 U가 있고, U의 부분집합들을 원소로 하는 집합 F 가 주어질 때

, F 의 우너소들인 집합들 중에서 어떤 집합들을 선택하여 합집합을 하면 U 와 같게 되는가 

*F에서 선택하는 집합들의 수를 최소화 하는 문제 

예제 문제 

응용

도시계획 

경비시스템 

기업의 경력 직원 고용

 

3.작업 스케줄링(Task Scheduling) 문제 

*작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 

시간 복잡도 O(nlogn)