[알고리즘] 동적 계획법(Dynamic Programming) - 0-1 배낭 문제

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

0-1 배낭 문제는 주어진 물건들을 배낭에 담을 때, 배낭의 용량을 초과하지 않으면서 가치를 최대화하는 문제이다. 각 물건은 한 번만 선택할 수 있다.

• 0은 물건을 담지 않는 것, 1은 물건을 담는 것을 의미한다.

1.1. 문제 정의

• 물건: 각 물건은 무게와 가치를 가진다.
• 배낭의 용량: 배낭이 담을 수 있는 최대 무게를 의미한다.
• 목표: 배낭의 용량을 초과하지 않으면서 선택한 물건들의 가치를 최대화하는 것이다.

1.2. 예시

• 물건 목록:
  • 물건 1: 무게 2, 가치 3
  • 물건 2: 무게 3, 가치 4
  • 물건 3: 무게 4, 가치 5
  • 물건 4: 무게 5, 가치 6
• 배낭의 용량: 5
• 최적의 선택: 물건 1과 물건 2를 선택하면 총 무게는 5이고, 총 가치는 7이 된다.

1.3. 동적 계획법을 통한 해결

0-1 배낭 문제를 해결하기 위해 동적 계획법을 사용할 수 있다. 다음과 같은 점화식을 세울 수 있다.

• dp[i][w]는 첫 $i$개의 물건 중에서 최대 무게 $w$를 초과하지 않으면서 얻을 수 있는 최대 가치를 저장한다.
• 초기값은 dp[0][w] = 0 (물건이 없을 때의 최대 가치).
• 점화식은 다음과 같다:
  • 물건 $i$를 선택하지 않는 경우: dp[i][w] = dp[i-1][w]
  • 물건 $i$를 선택하는 경우: dp[i][w] = dp[i-1][w - weight[i]] + value[i] (단, $w \geq weight[i]$)

1.4 예시를 통한 dp 배열 채우기

• 물건 1: 무게 2, 가치 3
• 물건 2: 무게 3, 가치 4
• 물건 3: 무게 4, 가치 5
• 물건 4: 무게 5, 가치 6
• 배낭의 용량: 5

DP 테이블 초기화

DP 테이블을 초기화한다. dp[i][w]는 첫 $i$개의 물건을 사용하여 최대 무게 $w$를 초과하지 않으면서 얻을 수 있는 최대 가치를 저장한다. 초기값은 모두 0으로 설정한다.

dp[0][0] = 0, dp[0][1] = 0, dp[0][2] = 0, dp[0][3] = 0, dp[0][4] = 0, dp[0][5] = 0

DP 테이블 채우기

1. 물건 1 (무게 2, 가치 3):
   • 배낭의 용량이 2 이상일 때만 물건 1을 선택할 수 있다.
   • $w = 0$ ~ $w = 1$: 물건 1을 선택할 수 없으므로 dp[1][w] = 0.
   • $w = 2$: 물건 1을 선택하여 가치 3을 얻을 수 있으므로 dp[1][2] = 3.
   • $w = 3$ ~ $w = 5$: 물건 1을 선택하여 가치 3을 얻을 수 있으므로 dp[1][3] = 3, dp[1][4] = 3, dp[1][5] = 3.

dp[1][0] = 0, dp[1][1] = 0, dp[1][2] = 3, dp[1][3] = 3, dp[1][4] = 3, dp[1][5] = 3

1. 물건 2 (무게 3, 가치 4):
   • $w = 0$ ~ $w = 2$: 물건 2를 선택할 수 없으므로 dp[2][w] = dp[1][w].
   • $w = 3$ ~ $w = 4$: 물건 2를 선택하여 가치 4를 얻을 수 있으므로 dp[2][3] = 4, dp[2][4] = 4.
   • $w = 5$: 물건 2를 선택하고 물건 1도 선택하여 가치 7을 얻을 수 있으므로 dp[2][5] = 7.

dp[2][0] = 0, dp[2][1] = 0, dp[2][2] = 3, dp[2][3] = 4, dp[2][4] = 4, dp[2][5] = 7

1. 물건 3 (무게 4, 가치 5):
   • $w = 0$ ~ $w = 3$: 물건 3을 선택할 수 없으므로 dp[3][w] = dp[2][w].
   • $w = 4$: 물건 3을 선택하여 가치 5를 얻을 수 있으므로 dp[3][4] = 5.
   • $w = 5$: 물건 3을 선택하지 않으므로 dp[3][5] = dp[2][5].

dp[3][0] = 0, dp[3][1] = 0, dp[3][2] = 3, dp[3][3] = 4, dp[3][4] = 5, dp[3][5] = 7

1. 물건 4 (무게 5, 가치 6):
   • $w = 0$ ~ $w = 4$: 물건 4를 선택할 수 없으므로 dp[4][w] = dp[3][w].
   • $w = 5$: 물건 4를 선택하여 가치 6을 얻을 수 있지만 물건 4를 선택하지 않는 경우가 더 높은 가치를 가지므로 dp[4][5] = dp[3][5].

dp[4][0] = 0, dp[4][1] = 0, dp[4][2] = 3, dp[4][3] = 4, dp[4][4] = 5, dp[4][5] = 7

최종 DP 테이블

• 최종적으로 dp[4][5]의 값인 7이 최대 가치이다. 이 값은 배낭의 용량을 초과하지 않으면서 선택한 물건들의 최대 가치를 나타낸다.
• 최종 DP 테이블은 다음과 같다:

dp[0][0] = 0, dp[0][1] = 0, dp[0][2] = 0, dp[0][3] = 0, dp[0][4] = 0, dp[0][5] = 0
dp[1][0] = 0, dp[1][1] = 0, dp[1][2] = 3, dp[1][3] = 3, dp[1][4] = 3, dp[1][5] = 3
dp[2][0] = 0, dp[2][1] = 0, dp[2][2] = 3, dp[2][3] = 4, dp[2][4] = 4, dp[2][5] = 7
dp[3][0] = 0, dp[3][1] = 0, dp[3][2] = 3, dp[3][3] = 4, dp[3][4] = 5, dp[3][5] = 7
dp[4][0] = 0, dp[4][1] = 0, dp[4][2] = 3, dp[4][3] = 4, dp[4][4] = 5, dp[4][5] = 7

물건/용량	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3
2	0	0	3	4	4	7
3	0	0	3	4	5	7
4	0	0	3	4	5	7

• 행: 각 행은 물건의 인덱스를 나타낸다. 예를 들어, 1행은 첫 번째 물건을 나타낸다.
• 열: 각 열은 배낭의 용량을 나타낸다. 예를 들어, 2열은 배낭의 용량이 2라는 의미이다.
• 값: 각 셀의 값은 해당 물건과 그 이전 물건들을 전부 고려했을 때 배낭의 용량에서 얻을 수 있는 최대 가치를 나타낸다.

1.5. 0-1 배낭 문제 구현

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    size_t n, capacity;
    std::cin >> n >> capacity;

    std::vector<int> weights(n);
    std::vector<int> values(n);
    
    for (size_t i = 0; i < n; i++) {
        std::cin >> weights[i] >> values[i];
    }

    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

    for (size_t i = 1; i <= n; i++) {
        for (size_t w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = std::max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    std::cout << "Maximum Value: " << dp[n][capacity];

    return 0;
}

Algorithm Theory 카테고리 내 다른 글 보러가기