백준 12865: 평범한 배낭

Gold_V 난이도 문제를 C++로 풀이한 내용입니다. 각 물건마다 무게와 가치가 주어졌을 때, 주어진 최대 용량의 배낭에 물건들을 담아 얻을 수 있는 최대 가치 합을 구하는 문제입니다.

문제 소개

• 문제 번호: 12865
• 문제명: 평범한 배낭
• 난이도 (티어): Gold_V
• 사용 언어: C++
• 실행 시간: 40 ms
• 메모리: 42004 KB
• 문제 요약: N개의 물건과 배낭의 최대 무게 W가 주어집니다. 각 물건은 무게와 가치를 가지며, 배낭에 담을 수 있는 물건들의 총 무게가 W를 초과하지 않도록 하면서 얻을 수 있는 가치의 총합을 최대로 하는 문제입니다.

접근 방법

이 문제는 전형적인 배낭 문제(Knapsack Problem)로, 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 각 물건을 넣거나 넣지 않는 두 가지 경우를 고려하여 최적의 해를 찾습니다.

• 알고리즘/자료구조: 동적 계획법(Dynamic Programming), 2차원 배열 (DP 테이블)
• 선택 이유: 각 물건에 대해 '넣는다' 또는 '넣지 않는다'의 선택지가 있으며, 이러한 선택들이 이전 상태의 결과에 의존하기 때문에 동적 계획법이 적합합니다. 또한, 중복되는 부분 계산을 피하고 최적의 해를 효율적으로 구할 수 있습니다.

풀이 과정

DP 테이블 dp[i][w]는 i번째 물건까지 고려했을 때, 최대 용량이 w인 가방에서의 최대 가치 값을 저장합니다.

1. DP 테이블 초기화:

   • dp 테이블은 (N + 1) x (W + 1) 크기로 생성합니다.
   • dp[0][w]는 0으로 초기화합니다. (물건이 0개일 때는 가치가 0)
   • dp[i][0]는 0으로 초기화합니다. (가방 용량이 0일 때는 아무것도 담을 수 없어 가치가 0)

2. DP 테이블 채우기:

   • i는 1부터 N까지, w는 0부터 W까지 순회합니다.
   • 현재 물건 i의 무게를 weight, 가치를 value라고 합니다.
   • 경우 1: 현재 물건 i를 배낭에 넣을 수 있는 경우 (weight <= w)
     • dp[i][w]는 다음 두 값 중 더 큰 값으로 갱신됩니다.
       • dp[i - 1][w]: 현재 물건 i를 넣지 않는 경우. 이전 물건들까지의 최대 가치.
       • dp[i - 1][w - weight] + value: 현재 물건 i를 넣는 경우. (i-1번째 물건까지 고려하여 w-weight 용량에 담을 수 있는 최대 가치 + 현재 물건 i의 가치)
   • 경우 2: 현재 물건 i를 배낭에 넣을 수 없는 경우 (weight > w)
     • dp[i][w]는 dp[i - 1][w]로 갱신됩니다. (현재 물건을 넣을 수 없으므로 이전 상태 그대로 유지)

3. 최종 결과:

   • 모든 물건을 고려하고 최대 용량 W일 때의 최대 가치는 dp[N][W]에 저장됩니다.

주의할 점:

• 배열 인덱스를 1부터 시작하도록 하여 물건의 개수와 용량에 맞춰 DP 테이블 크기를 설정합니다.
• w - weight 계산 시 음수가 되지 않도록 weight <= w 조건을 명확히 합니다.

코드 설명

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

    // DP 테이블 구조
    // dp[i][w] = i번째 물건까지 고려했을 때, 최대용량이 w인 가방에서의 최대 가치 값
    //
    // 테이블 구조 (예: N=3, W=10):
    //  i(번째 물건)\   w(최대용량)=0  1  2  3  4  5  6  7  8  9  10
    //  0              0          0  0  0  0  0  0  0  0  0  0  0 <= 0번째 물건 : 가치 0으로 초기화
    //  1              0          0  1  2  3  4  5  6  7  8  9  10 <= 그 상태(i,w)에서의 최대가치값들 계산순서
    //  2              0          0  A  B  C  D  E  F  G  H  ..
    //  3              0          0  ....                       30 <= 문제서 제시한 최대용량 W
    //                            ^=용량이 0이면 가치는 0 
    // 계산 순서 (각 칸에 번호를 매기면):
    // 000000000000        dp[i-1][w-weight] + value, dp[i-1][w]
    // 0123456789AB                      \               | 
    // 0CDEFGHIJKL                        \              | 안 넣는 경우는 유지만
    // 0MNOPQRSTUV                         \             | 넣는 경우는 둘 중 더 큰 값으로.
    //                                      \=>dp[i][w]<=| 
    // 각 칸은 윗칸과 왼윗칸만 참조
    // → 이전 물건 단계(i-1)의 두 용량 상태(w, w - weight) 둘 중에 더 큰 최대가치값을 i,w에 채택


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, W;
    cin >> N >> W;
    
    // 1-indexed
    // items에 각 물건의 무게와 가치 입력 
    vector<pair<int, int>> items(N + 1);
    items[0] = {0, 0};
    
    for (int i = 1; i <= N; i++) {
        int w, v;
        cin >> w >> v;
        items[i] = {w, v};
    }
    
    // N + 1 바이 M + 1 크기의 dp 테이블 생성
    // 첫 행과 첫 열을 0으로 초기화
    // dp[0][w] = 0 (물건이 0개면 가치는 0)
    // dp[i][0] = 0 (용량이 0이면 아무것도 못 넣으므로 가치는 0)
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    
    // DP 계산
    for (int i = 1; i <= N; i++) {
        int weight = items[i].first;
        int value = items[i].second;
        
        for (int w = 0; w <= W; w++) {
            // i번째 물건을 넣을 수 있는 경우
            if (weight <= w) { // 넣을 수 있더라도 안넣는 게 이득이면 안 넣고 유지해야하니까 비교해보자
                // 윗칸(dp[i - 1][w]), 
                // 왼윗칸(dp[i - 1][w - weight] + value) 중 최대가치값이 더 큰 값을 i,w에 채택
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value);
            
            } 
            // i번째 물건을 넣을 수 없는 경우
            else { 
                dp[i][w] = dp[i - 1][w]; // 물건을 못 넣으므로 이전 상태 유지 : 바로 윗칸 참조 
            }
        }
    }
    
    // 모든 물건을 고려했을 때, 전체 용량 W에서의 최대 가치
    cout << dp[N][W];
    
    return 0;
}

• ios_base::sync_with_stdio(false); cin.tie(NULL);: 입출력 속도 향상을 위한 설정입니다.
• vector<pair<int, int>> items(N + 1);: 각 물건의 무게와 가치를 저장할 벡터입니다. 1-indexed로 사용하기 위해 크기를 N + 1로 설정합니다. items[0]은 더미 데이터입니다.
• vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));: DP 테이블입니다. dp[i][w]는 i번째 물건까지 고려했을 때, 최대 용량이 w인 배낭의 최대 가치를 의미합니다. 모든 값을 0으로 초기화합니다.
• for (int i = 1; i <= N; i++): 각 물건에 대해 순회합니다.
• for (int w = 0; w <= W; w++): 현재 물건 i를 고려할 때, 가능한 모든 용량 w에 대해 DP 테이블을 갱신합니다.
• if (weight <= w): 현재 물건 i의 무게가 현재 고려 중인 용량 w보다 작거나 같은 경우, 즉 물건을 담을 수 있는 경우입니다.
• dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value);: 물건을 넣지 않는 경우(dp[i - 1][w])와 넣는 경우(dp[i - 1][w - weight] + value) 중 더 큰 가치를 선택합니다.
• else { dp[i][w] = dp[i - 1][w]; }: 물건을 담을 수 없는 경우, 이전 상태의 가치를 그대로 유지합니다.
• cout << dp[N][W];: 최종적으로 N개의 물건을 모두 고려했을 때, 최대 용량 W에 담을 수 있는 최대 가치를 출력합니다.

복잡도 분석

• 시간 복잡도: O(N * W)
  • DP 테이블을 채우는 데 N개의 물건과 W개의 용량에 대해 이중 반복문이 사용됩니다.
• 공간 복잡도: O(N * W)
  • DP 테이블 dp를 저장하기 위해 (N + 1) x (W + 1) 크기의 2차원 배열이 사용됩니다. (공간 복잡도를 O(W)로 최적화할 수도 있습니다.)

배운 점

이 문제를 통해 동적 계획법의 기본적인 배낭 문제(0/1 Knapsack Problem) 해결 방법을 익혔습니다. DP 테이블의 상태 정의, 전이 조건, 그리고 초기화의 중요성을 다시 한번 깨달았습니다. 특히, 현재 상태를 결정하기 위해 이전 상태의 여러 값을 어떻게 조합해야 하는지를 명확히 이해할 수 있었습니다. 또한, 시간 복잡도와 공간 복잡도를 고려하여 효율적인 DP 테이블 설계의 중요성을 배웠습니다.