Greedy Algorithm

탐욕 알고리즘

• 최적의 해에 가까운 값을 구하기 위해 사용된다
• 매순간 최적이라고 생각되는 경우를 선택하는 방식
  • 이것이 최종적으로 최적임을 암시하는것은 아니다

예시

동전 문제

지불해야하는 금액이 4720원 일 때, 1, 50, 100, 500원 동전으로 동전수가 가장적게 지불해라

• 가장 큰 동전부터 작은 동전순으로 값을 채워야 한다

public static void main(String[] args) {
	List<Integer> coins = new ArrayList<>();
	coins.add(1);
	coins.add(50);
	coins.add(100);
	coins.add(500);
	Collections.reverse(coins);
	System.out.println(coin_Count(coins, 4720));
}
private static int coin_Count(List<Integer> coins, int money) {
	int total_coin = 0;

	while (coins.size() > 0) {
		int count = money / coins.get(0);
		total_coin += count;
		money -= count * coins.get(0);
		coins.remove(0);
	}
	return total_coin;
}
//출력
31개

부분 베낭 문제

무게 제한이 k인 베낭에 최대가치를 가지도록 물건을 넣는 문제

• 각 물건은 무게(w)와 가치(v)로 표현될 수 있다
• 물건을 쪼갤수 있어서 일부분을 넣을수 있는 Fraction Knapsack Problem
• 물건을 쪼개서 넣을수 없는 0/1 Knapsack Problem

구현

먼저 무게 대비 가치가 높은 순서로 정렬
가장 무게 대비 가치가 높은 순서대로 최대로 채워 나간다
즉, 뒤의 조합은 고려하지 않고 일단 가장 가치가 높은 값을 모두 넣고 진행

WVclass wv1 = new WVclass(20, 10);
WVclass wv2 = new WVclass(10, 10);
WVclass wv3 = new WVclass(25, 8);
WVclass wv4 = new WVclass(30, 5);
WVclass wv5 = new WVclass(15, 12);
WVclass[] wVarr = {wv1, wv2, wv3, wv4, wv5};
System.out.println(knapsack(wVarr, 30));
private static double knapsack(WVclass[] arr, int capacity)
{
	//무게대비 가치가 높은 순서로 정렬
    Arrays.sort(arr, (o1, o2) -> {
		int first = o1.V * 100 / o1.W;
		int second = o2.V * 100 / o2.W;
		return second - first;
	});

	double total_value = 0;
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < arr.length; i++){
		if (capacity - arr[i].W >= 0) {
			capacity -= arr[i].W;
			total_value += arr[i].V;
			sb.append(arr[i].W +" "+arr[i].V+" .. ");
		}
		else
		{
			double fraction = ((double)capacity / (double)arr[i].W);
			capacity -= (double)arr[i].W * fraction;
			total_value += (double)arr[i].V * fraction;
			sb.append(arr[i].W +" "+arr[i].V+" .. ");
		}
	}
	System.out.println(sb);
	return total_value;
}
//출력
10 10 .. 15 12 .. 20 10 .. 25 8 .. 30 5 .. 
24.5 //<- 30의 무게 제한내에서 모은 최대 가치 

탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용한다
• 매 순간마다 최적의 판단을 할뿐이지 최종적으로 최적의 판단을 하는 것이 아니다