[알고리즘] 배낭 알고리즘 (fractional 배낭, 0-1 배낭)

분할 가능한(fractional) 배낭 알고리즘

문제

도둑은 W만큼 들 수 있는 가방을 가지고 있다. W를 초과하는 보석을 담을 경우 가방이 찢어져 버리고 만다. 무게가 w고 가치가 v인 N개의 보석이 존재할 때 도둑이 훔칠 수 있는 보석의 최대 가치를 구하라. (보석은 분할 가능하다.)

 

 

그리디 알고리즘을 다룰 때 가장 자주 나오는 문제이다. 브루트포스를 사용해 훔칠 수 있는 보석의 모든 조합을 구할 수 있겠지만 N개의 보석의 모든 조합을 구하려면 O(2^N)의 시간이 걸릴 것이다. (보석을 훔친다 || 안 훔친다.) * N개

 

따라서 그리디하게 접근하면 효율적으로 해결할 수 있다. 무게 대비 가치가 높은 것부터 가방을 채우면 되지 않을까? N개의 보석을 v/w가 높은 순으로 정렬 후 W만큼까지만 훔쳤을 때 가치의 합을 구하면 된다.

 

 

0-1 배낭 알고리즘

분할가능한 배낭 문제와 다른 점은 보석을 온전히 그 상태로 취해야 한다는 점이다. 

 

문제

만약 도둑이 10kg 가방을 가지고 있을 때, 4개의 보석(8kg 9$, 3kg 3$, 3kg 3$, 4kg 4$)가 있다고 하자. 보석들의 무게 대비 가치는 다음과 같다.

• 8kg 9$ : 9 / 8 =1.125
• 3kg 3$ : 3 / 3 = 1
• 3kg 3$ : 3 / 3 =1
• 4kg 4$ : 4 / 4 =1

 

만약 이 문제를 그리디하게 접근한다면 8kg 9$ 보석 하나만 가져가 최대 9$의 가치를 취하겠지만, 실제로는 가치가 작은 보석일지라도 더 많이 들어서 10$의 가치를 얻을 수 있는 상황이 존재한다. 따라서 '분할 가능한' 배낭 문제와 다르게 접근해야 한다.

 

1. 다이나믹 프로그래밍

i번째 보석에 대해서 i-1번째 보석의 결과를 사용해 최적해를 구하는 방법이다. dp[i][j]의 의미는 도둑이 i번째 보석까지 j 무게만큼 훔쳤을 때 가질 수 있는 최대 가치이다.

i번째 보석을 훔쳤을 때 무게가 W를 넘지 않는다면 i-1번째 결과와 비교해서 최대 가치를 구할 수 있다.

int dp[N][K], N, K; // N<=100, K<=100,000
//...

for(int i(1);i<=N;i++){
    for(int j(1);j<=K;j++){
        dp[i][j]=dp[i-1][j];
        if(j-weight[i]>=0){
            dp[i][j]=max(dp[i][j], dp[i-1][j-weight[i]]+value[i]);
        }
    }
}

 

단, N과 K의 값이 커질수록 시간복잡도 O(NK)와 공간복잡도가 높아질 것이다.

 

 

2. 백트래킹

보석을 훔칠 경우, 훔치지 않을 경우를 모두 따져 완전 탐색하는 방법이다. 자칫하면 브루트포스처럼 보일테지만 유망하지 않은 경우(훔친 무게가 W를 초과하는 경우)는 더이상 진행하지 않아 나름 효율적이다.

 

 

 

 

 

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

12865번: 평범한 배낭

 

 

+)

배낭 문제는 N과 W가 커질 경우 다항시간 내 최적해를 찾아내지 못한다. 따라서 NP-problem 이다. (P-problem 은 다항시간 내 해결할 수 있는 문제)