배낭 문제 (Knapsack Problem)

 

목차

 

 

배낭 문제 (Fractional Knapsack Problem)

"배낭 문제"는 한정된 조건에서 최대 가치를 구하는 최적화 문제를 의미하는 용어이며, DP이외에도 백트래킹 등으로 구현할 수 있다.

효율성으로 인해 DP를 많이 사용하지만, DP로만 접근할 수 있음을(혹은 DP기법 자체를) 의미하진 않는다.

 

1. 분할 가능한 배낭 문제 (Fractional Knapsack Problem)

그리디한 방법으로 풀 수 있다.

아이템들의 "무게당 가치"를 구한 후, 이를 내림차순으로 정렬하여 무게 제한에 도달할 때까지 더해주면 된다.

 

다만, 무게당 가치 = 가치/무게는 즉 무게 1당 가치를 의미한다.

무게 = 0.1 가치 = 0.5 일 때, 가치/무게 = 0.5/0.1 = 5

 

이 경우, 다음과 같이 가방의 무게가 소수(Decimal)인 경우 최적해를 보장할 수 없다.

아이템 A: 무게 2, 가치 10
아이템 B: 무게 3, 가치 12
배낭의 무게 = 12.5일 때,

when 1
아이템 A: 무게 1, 가치 5
아이템 B: 무게 1, 가치 4

 

이런 경우는 배낭의 무게를 나누어 떨어지게 하는 값으로 무게당 가치를 설정해야 한다. (무게가 12.5일 때 0.5, 0.1 등등)

when 0.5
아이템 A: 무게 0.5, 가치 2.5
아이템 B: 무게 0.5, 가치 2

 

2. 0-1 배낭 문제 (0-1 Knapsack Problem)

Bounded Knapsack Problem의 종류로, 0-1은 이진(선택하지 않음/선택함)을 의미한다.

즉, 아이템별 개수가 최대 1개인 배낭 문제이다.

 

최대 가치 탐색을 가정하면, 다음과 같은 코드를 작성한다.

        // when (j >= cost) 
        dp[i][j] = Math.max(dp[i - 1][j - cost] + value, dp[i - 1][j]);
        // else
        dp[i][j] = dp[i - 1][j]);

1. j >= cost는 현재 물건을 넣을 수 있음을 의미한다.

2. dp[i - 1][j - cost] + value는 이전 물건을 고려한 경우에서 현재 물건을 1개 넣는 경우를 의미한다.

3. dp[i - 1][j]는 현재 물건을 넣지 않는 경우를 의미한다. (넣을 수 없을 때나, 넣어도 최적이 아닐때 사용된다.)

 

두 경우 중 최적의 값을 기록한다.

 

3. 개수 제한없는 배낭 문제 (Unbounded Knapsack Problem)

1. 비 효율적인 방법 (중복 연산 존재)
// when (j - cost >= 0)
        dp[i][j] = Math.max(dp[i - 1][j - cost] + value, Math.max(dp[i][j - cost] + value, dp[i - 1][j]));
        // else
        dp[i][j] = dp[i - 1][j]);
        
2. 일반적인 방법
// when (j - cost >= 0)
        dp[i][j] = Math.max(dp[i][j - cost] + value, dp[i - 1][j]);
        // else
        dp[i][j] = dp[i - 1][j]);

 

1번의 경우에서,

1. j >= cost는 현재 물건을 넣을 수 있음을 의미한다.

2. dp[i - 1][j - cost] + value는 이전 물건을 고려한 경우에서 현재 물건을 넣는 경우를 의미한다.

3. dp[i][j - cost] + value는 이전+현재 물건을 고려한 경우에서 현재 물건을 넣는 경우를 의미한다.

(정확히는, 이전 물건을 각각 m0..mi-1개, 현재 물건을 mi개 넣은 상태에서 현재 물건 1개를 넣는)

4. dp[i - 1][j]는 현재 물건을 넣지 않는 경우를 의미한다. (넣을 수 없을 때나, 넣어도 최적이 아닐때 사용된다.)

 

하지만, 위의 코드에서 2번 과정은 중복 연산이 된다.

dp[i][j - cost]를 구할 때, 우린 이미 dp[i - 1][j - cost]를 고려하여 dp[i][j - cost]를 구성하였다.

 

그림판 ㅎㅎ;

j - cost를 A로 치환하면,

우리는 dp[i][j]을 구하는 과정 dp[i][j] = Math.max(dp[i][A] + value, dp[i - 1][j])에서,

dp[i][A] = Math.max(dp[i][A - cost], dp[i - 1][A])을 이전에 수행했기 때문에,

dp[i][j] = Math.max(dp[i - 1][A] + value , dp[i - 1][j])이 자동으로 이루어진다. 따라서, 중복 연산을 제거한다.