탐욕 알고리즘(Greedy Algorithm)

1. 탐욕 알고리즘

• Greedy algorithm이라고 부름
• 최적의 해에 가까운 값을 구할 때 사용한다.
• 여러 경우 중 하나를 결정할 때마다, 매순간 "최적"이라고 생각되는 경우를 선택해서 최종적인 값을 구한다.

2. 탐욕 알고리즘 예

문제 1: 동전 문제

- 지불해야 하는 값이 4720원일 때,

  1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하는 방식

<해결 방식>

1. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식

public class Main {
    public static void main(String[] args) {
        // 만약 동전 리스트가 내림차순으로 정렬되지 않을 경우
        // 정렬을 해주어야 한다. sort
        int[] list = {500, 100, 50, 1};
        System.out.println(coinCount(4720, list));
    }
    public static int coinCount(int value, int[] coinList){
        int totalCount = 0;
        for(int i = 0; i < 4; i++){
            // 가장 큰 동전의 수부터 value를 나눈 몫(개수)
            int curCoin = value / coinList[i];
            totalCount += curCoin;
            value -= curCoin * coinList[i];
        }
        return totalCount;
    }
}

문제 2: 부분 배낭 문제 (Fractional Knapsack Problem)

• 무게 제한이 k인 배낭에 최대 가치(v)를 가지도록 넣는 문제
  • 각 물건은 무게(w)와 가치(v)로 표현될 수 있다.
  • 물건은 쪼갤 수 있으므로 물건의 일부가 배낭에 넣어질 수 있다.

물건(i)	물건 1	물건 2	물건 3	물건 4	물건 5
무게(w)	10	15	20	25	30
가치(v)	10	12	10	8	5

<해결 방식> 

• 문제 그대로 무게가 적고 가치가 높은 물건을 채우는 것이 중요하다.

import java.util.*;

class Node{
    public int weight;
    public int value;

    public Node(int w, int v){
        this.weight = w;
        this.value = v;
    }
}
public class Main {
    public static void main(String[] args) {

        ArrayList<Node> data = new ArrayList<>();
        int capacity = 30;

        // 표에 있는 데이터 입력
        data.add(new Node(10, 10));
        data.add(new Node(15, 12));
        data.add(new Node(20, 10));
        data.add(new Node(25, 8));
        data.add(new Node(30, 5));

        // 가치/무게로 나눈 비율이 높은 순으로 정렬
        Collections.sort(data, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                double ratioA = (double) o1.value / o1.weight;
                double ratioB = (double) o2.value / o2.weight;
                return Double.compare(ratioB, ratioA);
            }
        });
        System.out.println(getMaxValue(data, capacity));
    }
    public static double getMaxValue(List<Node> list, int capacity){
        double totalValue = 0;

        for(int i = 0; i < list.size(); i++){
            // 총량 >= 물건의 무게일 떄,
            if(capacity - list.get(i).weight >= 0){
                capacity -= list.get(i).weight;
                totalValue += list.get(i).value;
            }else {
                // 총량 < 물건의 무게일 때,
                // 총량 / 무게를 해서 나온 fraction을
                // 값과 곱해 더해준다.
                double fraction = (double) capacity / list.get(i).weight;
                totalValue += list.get(i).value * fraction;
                break;
            }
        }
        return totalValue;
    }
}