탐욕알고리즘GreedyAlgorithm

최적의 해에 가까운 값을 구하기 위해 사용됨
여러 경우중 매순간 최적이라고 생각되는 경우를 선택하는 방식

동전문제
4720 원을 지불해야함
1, 50, 100, 500 원짜리 동전을 사용함
동전의 수가 가장 적게 지불하시오

첫번째 단계에서 최선의 선택은 500원 으로 4500원 지불
두번째 단계에서 최선의 선택은 100원 으로 200원 지불
세번째 단계에서 최선의 선택은 1원 으로 20원 지불

부분 배낭 문제9(Fractional Knapsack Problem)
무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는문제
물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있다

물건을 이차원 배열로 담았다
Integer[][] products = {{10, 10}, {15, 12}, {20, 10}, {25, 8}, {30, 5}};
원소안의 첫숫자는 무게, 둘째는 가치

public class FractionalKnapsackProblem {

    FractionalKnapsackProblem(){}
    
    float fkp(int k, Integer[][] product)
    {
        float result = 0;

        Arrays.sort(product, new Comparator<Integer[]>(){
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return (o2[1]/o2[0])-(o1[1]/o1[0]);//compare value per weight
            }
        });

        float totalValue = 0;
        int totalWeight = 0;
        for(int i = 0; i < product.length; ++i)
        {
            if(product[i][0] < k)
            {
                k -= product[i][0];
                totalValue += product[i][1];
                totalWeight += product[i][0];

                System.out.println("Weight added: " + product[i][0]);
                System.out.println("Value added: " + product[i][1]);
            }
            else
            {
                totalValue += ((float)product[i][1] / (float)product[i][0]) * (float)k;
                totalWeight += k;
                System.out.println("Weight added: " + k);
                System.out.println("Value added: " + ((float)product[i][1] / (float)product[i][0]) * (float)k);
                k = 0;
            }

            if(k == 0)
                break;
        }

        System.out.println("Total value: " + totalValue + ", Total weight: " + totalWeight);

        return result = totalValue;
    }
}

public class GreedyTest {

    public static void main(String[] args) {

        FractionalKnapsackProblem fkpinstance = new FractionalKnapsackProblem();

        Integer[][] products = {{10, 10}, {15, 12}, {20, 10}, {25, 8}, {30, 5}};

        System.out.println(fkpinstance.fkp(55, products));
    }
}