[알고리즘] 욕심쟁이 알고리즘

백준코딩에서 발견한 배낭문제입니다.

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

배낭문제에서 최소 물품을 가지고 가장 가치 있는 물건을 가져갈 때 최대 이익을 구하는 문제예요.

 

이번에 알고리즘을 아주 살~~ 짝 터치해 보면서 범접해 볼 수 없는 어려움을 느꼈더랬죠.. ㅎㅎ;;

 

위 문제와 같은 문제인데 한번 아래 문제를 풀어볼까요?

문제 풀어보기

[01] 용량이 20인 배낭이 있다. 물체의 이익과 무게가 다음과 같이 주어져 있고 이들 물체를 쪼개 넣을 수 있다고 할 때 배낭에 넣기 위한 진행 과정과 최대 이익을 구하시오.

 

(2,8), (3,15), (7,21), (4,28), (6,36)

 

※ 해설

 

위 문제에서 이익이 가장 큰 물체를 최대한 배낭에 넣어야 하니 내림차순으로 정렬하고 무게당 이익이 가장 큰 물체부터 배낭에 넣고 과정을

반복하면 됩니다.

 

M = 20, n= 5

(p1, p2, p3, p4, p5) = (8,15,21,28,36)

(w1, w2, w3, w4, w5) = (2,3,7,4,6)

M = 용량, n = 물체 개수, p = 물체 이익, w = 물체 무게

 

그리고 p/w를 개수별로 진행합니다.

 

단위 무게당 이익은 다음계산과 같습니다.

 

(8/2, 15/3, 21/7 28/4, 36/6) = (4,5,3,7,6)

 

내림차순으로 정렬하면 (p4, p5, p2, p1, p3)

 

배낭에 p4를 모두 넣으면 이익 28, 남은 용량 16이 됩니다.

배낭에 p5를 모두 넣으면 이익 36, 남은 용량 10이 됩니다.

배낭에 p2를 모두 넣으면 이익 15, 남은용량 7이 됩니다.

배낭에 p1을 모두 넣으면 이익 8, 남은 용량 5가 됩니다.

 

여기까지 모든 이익을 합치면 28+36+15+8입니다. 총 87

 

배낭에 p3을 모두 넣을 수 없습니다.(무게가 7이기 때문에)

 

그래서 남은 배낭의 용량은 5만큼 물체를 쪼개서 넣어야 합니다..

 

무게 7을 5만큼 쪼개려면 5/7을 합니다.

 

그리고 p3의 총이익은 21이니 그 값의 *21을 합니다.

(5/7)*21은 15입니다.

 

그러면 배낭엔 모든 용량을 다 넣으며 87에 이익 15를 더해서

욕심쟁이 알고리즘을 사용하여 넣을 수 있는 최대 이익은 102가 됩니다.

 

 

자바 코드로 표현해본다면 다음과 같이 표현해볼 수 있습니다.

public class KnapsackProblem {
    public static int knapsack(int W, int[] wt, int[] val, int n) {
    //욕심쟁이 알고리즘 메서드
        int[][] dp = new int[n + 1][W + 1];

        // 초기화
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W];
    }

    public static void main(String[] args) {
    //상황 가정해보기
        int W = 20;
        int[] wt = { 2, 3, 7, 4, 6 };
        int[] val = { 8, 15, 21, 28, 36 };
        int n = val.length;

        System.out.println("Maximum value that can be obtained: " + knapsack(W, wt, val, n));
    }
}