백준 #12865. 평범한 배낭

백준 #12865. 평범한 배낭

정리

• 다이나믹 프로그래밍 알고리즘 문제에서 항상 고민되는 부분은, 메모이제이션 기법을 이용할 때 ‘어떤 메모리(값)를 저장해 둘 것인가'이다.

• 이 문제 같은 배낭 문제에서는, 물건을 넣을 수 있는 전체 배낭 용량에 한계가 있으므로, ‘배낭 용량'을 메모이제이션에서 반드시 고려해야 한다.

• $i$번째 물건을 담는 상황이고, 배낭 용량(버틸 수 있는 무게)가 $j$라고 할 때의 배낭에 넣을 수 있는 물건들의 가치의 합의 최댓값을 $dp(i, j)$라 하면, 이 문제를 해결할 수 있는 점화식은 아래와 같다.

  $dp(i,~j) = \begin{cases} max\{dp(i-1,~j),~V(i)~+~dp(i-1,~j-W(i)) \} &\text{if }~j-W(i)\geq0, \\ dp(i-1,~j) &\text{if } ~j-W(i)\leq0. \end{cases}$

  ($W(i)$는 $i$번째 물건의 무게, $V(i)$는 $i$번째 물건의 가치를 뜻한다.)

  이 점화식과 아래 정답 코드에 적혀 있는 주석을 같이 참고하면 되겠다.
  
  

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int N, K;
    int W[101];
    int V[101];
    int dp[101][100001];
    // dp 2차원 배열의 바깥쪽은 i번째 물건일 때, 안쪽은 버틸 수 있는 무게가 j일 때의 값을 저장한다.
    
    cin>>N>>K;
    for (int i=1; i<=N; i++) {
        cin>>W[i]>>V[i];
    }
    
    // default 값 설정. 0번째 물건은 존재하지 않으므로 0으로 초기화.
    for(int i=0; i<=K; i++) {
        dp[0][i] = 0;
    }
    // default 값 설정. 배낭의 용량이 0이면 아무것도 넣을 수 없으므로 0으로 초기화.
    for(int i=0; i<=N; i++) {
        dp[i][0] = 0;
    }
    // 배낭의 용량이 j라고 할 때, i번째 물건을 넣을 수 있을까?
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=K; j++) {
            if (j - W[i] < 0) {
                // i번째 물건의 무게가 j보다 커서 넣을 수 없을 때
                dp[i][j] = dp[i-1][j];
            }
            else {
                // 무게가 j보다 작다면 가능한 두 가지 case 중 최댓값을 넣어준다.
                // 1. i번째 물건을 넣지 않은 경우
                // 2. i번째 물건을 넣는 경우 (이때는, i-1번째까지 넣었을 때, 남은 용량이 W[i]만큼은 확보되어 있어야 한다.)
                dp[i][j] = max(dp[i-1][j], V[i] + dp[i-1][j-W[i]]);
            }
        }
    }
    
    cout<<dp[N][K]<<endl;
    return 0;
}