Greedy 알고리즘 - Fractional knapsack Problem, 집합 커버 문제
Greedy 알고리즘의 네 번째 문제
4.부분 배낭 문제
-n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있다. 배낭을 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 물건을 넣어라.
-배낭 문제의 종류
(1) 0-1 배낭 문제. 물건을 통째로 넣어야 한다. 이는 greedy알고리즘으로는 풀 수 없다.
(2) 부분 배낭 문제. 물건을 부분적으로 잘라서 담는 것을 허용한다. greedy 알고리즘으로 해결 가능하다.
-방법
단위 무게 당 가장 비싼 물건을 배낭에 넣고, 그 다음으로 값 나가는 물건을 넣음. 그러다 값나가는 물건을 통째로 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 부분적으로 나눠 배낭에 넣음
-Pseudo Code
Input : n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
Output : 배낭에 담은 물건 리스트 L, 배낭에 담은 물건 가치의 합 v
각 물건에 대해 단위 당 무게 가치를 계산한다.
물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬한다. 정렬된 물건 리스트를 S라고 한다.
L=공집합 ,W=0, v=0 //배낭 물건 리스트, 배낭 무게 합, 배낭 가치 합
S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져온다. 정렬되어있으므로 쉽다
while((w+weight(x))<=C){//배낭 무게와 x의 무게 합이 담을 수 있는 무게보다 적다면 담자.
x를 L에 추가한다.
w=weight+weight(x)//w값 업데이트
v=v+value(x)//v값 업데이트
x를 S에서 제거
S에서 단위 무게 당 가치가 가장 큰 물건 X를 가져옴}
if((C-w)>0){//배낭에 물건을 부분적으로 담을 수 있으면
x를 C-w만큼 L에 추가하자.
v=v+value(C-w)
return L,v}-Time Complexity
1.정렬 O(nlogn)
2.가방이 꽉 찰때까지 무게 당 가치가 큰 물건 찾기를 반복한다. S를 순환. O(n)
3.물건을 배낭에 넣는 과정은 constant하다.
4.물건을 나눠서 넣는 과정이 한 번뿐이라면 constant하다.
Time Complexity=O(nlogn)+O(n)=O(nlogn)
-소스코드
#include <iostream>
#include <algorithm>
#include <vector>
struct Object
{
int id;
int weight;
double value;
double value_per_unit_weight;
Object(int i, int w, double v) : id(i), weight(w), value(v),
value_per_unit_weight(v / w) {}
// std::sort()에서 사용
inline bool operator< (const Object& obj) const
{
return this->value_per_unit_weight < obj.value_per_unit_weight;
}
// 콘솔 출력 지원. std::cout << obj << std::endl; 코드 사용 가능
friend std::ostream& operator<<(std::ostream& os, const Object& obj);
};
std::ostream& operator<<(std::ostream& os, const Object& obj)
{
os << "[" << obj.id << "] 가격: " << obj.value
<< " \t무게: " << obj.weight
<< " kg\t단위 무게 당 가격: " << obj.value_per_unit_weight;
return os;
}
// 분할가능 배낭 문제 알고리즘 구현 함수
auto fill_knapsack(std::vector<Object>& objects, int knapsack_capacity)
{
std::vector<Object> knapsack_contents;
knapsack_contents.reserve(objects.size());
// 물건들을 내림차순으로 정렬 (단위 무게 당 가격 기준)
std::sort(objects.begin(), objects.end());
std::reverse(objects.begin(), objects.end());
// '가장 가치있는' 물건들 먼저 배낭에 추가
auto current_object = objects.begin();
int current_total_weight = 0;
while (current_total_weight < knapsack_capacity && current_object != objects.end())
{
knapsack_contents.push_back(*current_object);
current_total_weight += current_object->weight;
current_object++;
}
// 마지막 추가한 물건에 의해 배낭 최대 허용 무게가 초과된 경우
int weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity;
Object& last_object = knapsack_contents.back();
if (weight_of_last_obj_to_remove > 0)
{
last_object.weight -= weight_of_last_obj_to_remove;
last_object.value -= last_object.value_per_unit_weight * weight_of_last_obj_to_remove;
}
return knapsack_contents;
}
int main(int argc, char* argv[])
{
std::vector<Object> objects;
objects.reserve(7);
std::vector<int> weights{ 1, 2, 5, 9, 2, 3, 4 };
std::vector<double> values{ 10, 7, 15, 10, 12, 11, 5 };
for (auto i = 0; i < 7; i++)
{
objects.push_back(Object(i + 1, weights[i], values[i]));
}
// 사용할 수 있는 물건 정보 출력
std::cout << "[사용할 수 있는 물건 정보]" << std::endl;
for (auto& o : objects)
std::cout << o << std::endl;
std::cout << std::endl;
// 분할가능 배낭 문제 알고리즘 실행, 배낭의 최대 허용 무게는 7로 지정.
int knapsack_capacity = 7;
auto solution = fill_knapsack(objects, knapsack_capacity);
// 배낭에 넣을 물건 정보 출력
std::cout << "[배낭에 넣을 물건들 (최대 용량 = " << knapsack_capacity << ")]" << std::endl;
for (auto& o : solution)
std::cout << o << std::endl;
std::cout << std::endl;
}
greedy 알고리즘의 다섯 번째 문제
5.집합 커버 문제
-n개의 원소를 가진 집합 U={0,1,2,...,n-1} 이 있고, U개의 부분집합들을 원소로 하는 집합 F가 주어질때, F의 원소들인 집합들 중에서 어떤 집합을 선택하여 합집합하면 U와 같게 되는가?
-집합 F에서 선택하는 집합은 최소여야 한다.
-Greedy로는 풀 수 없다...
ex)신도시 학교 배치 문제
10개의 마을이 신도시에 만들어질 계획이다. 아래 두 가지 조건을 만족하도록 학교 위치를 선정해라
-학교는 마을(vertex)에 위치해야한다.
-등교 거리(edge)는 걸어서 15분 이내여야 한다.
한 마을에서 갈 수 있는 다른 마을의 모임을 하나의 집합이라고 볼때, 10개의 집합이 생긴다.
vertex1 마을에서 갈 수 있는 다른 마을은 2,3,8
vertex2 마을에서 갈 수 있는 다른 마을은 1,3,4,8
....
vertext10 마을에서 갈 수 있는 다른 마을은 10
이 집합이 모여서 전체 집합이랑 같아지려면(모든 마을에서 학교에 다닐 수 있으려면) 집합 수가 몇 개여야 할까? (학교 수가 몇 개여야 할까?)
-방법
1.가장 많은 vertex를 커버하는 set부터 선택한다.
2.커버하고 남은 vertex를 가장 많이 커버하는 set를 이어서 선택한다.
ex)
(1) 가장 많은 마을을 가까이 하는 마을은 4번 마을이다.
(2) 4번마을을 선택하면 2,3,4,5,7,8,마을은 커버되지만 1,6,9,10 마을이 남는다. 남은 마을을 가장 많이 가까이 하는 마을을 또 찾는다.
(3) 6번마을이 6,9,10을 커버한다.
(4) 남은 1번을 커버하기 위해 1을 가까이 하는 마을을 아무거나 하나 선택한다.
(5) 최종선택 4,6,1 마을
문제를 풀었지만 가장 효율적인 결과인 2,6 마을을 찾아내지는 못했다.
하지만 우리가 풀 수 있는 최선의 방법이다.
사실 beam search 알고리즘으로 풀 수 있다고 하나 여기선 다루지 않을 것이다.
-Pseudo Code
Input : U ,F={S(i)},i=1...n
Output : 집합 커버 C
C=공집합 //초기화시킨다.
while(U!=공집합)do{//U가 공집합이 될때까지 반복한다.
U의 원소들을 가장 많이 포함하고 있는 집합 S를 F에서 선택한다.//그리디
U=U-S//S의 원소들을 U에서 제거한다. U는 아직 커버되지 않은 원소들의 집합이므로.
S를 F에서 제거하고, S를 C에 추가한다.//선택된 집합은 F에서 제거, C에 추가
}
return C
-Time Complexity
1.(line2)while 루프 최대 n번 순환 O(n) =>루프 1번마다 원소가 1개씩만 커버되는 최악의 경우, n번 순환해야한다.
2.(line2)U가 공집합인지 조사 O(1) =>U의 현재 원소 수를 체크하는 변수를 두고, 0인지 확인한다.
3.(line3)1번 순환 안에서 원소를 가장 많이 포함하는 집합을 찾으려면 남아있는 set 각각을 U와 비교하여야 한다. O(n^2) =>S와 U와의 비교 =S의 수 * U의 수
4.(line4) 집합 U에서 집합S의 원소를 제거하는 것이므로 O(n) => 남은 원소 비교, 확인
5.(line5) : S를 F에서 제거하고, S를 C에 추가하는 것은 O(1)시간이 걸린다.
루프 1회의 시간복잡도
O(1)+O(n^2)+O(n)+O(1)=O(n^2)
알고리즘 전체의 시간복잡도
O(n)*O( n^2)=O(n^3)
지금까지 본 알고리즘 중에 가장 시간복잡도가 높지만 그래도 사용가능하다.
-사용예시
>도시 계획에서 공공기관 배치하기. 많은 사람들이 쉽게 찾을 수 있도록
>경비 시스템: 경비가 요구되는 장소의 CCTV 카메라의 최적 배치. 사각지대가 생기지 않도록 도면을 graph화 하여 계산
>컴퓨터 바이러스 찾기
>대기업의 구매 업체 선정
>기업의 경력 직원 고용
>그 외에도 비행기 조종사 스케줄링, 조립 라인 균형화, 정보 검색 등에 활용
-소스코드