[BOJ] 백준 12865 평범한 배낭 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

0-1 Knapsack Problem 과 동일한 문제이다.

 

N 개의 물건이 입력으로 주어진다. 각 무게 W , 가치 V 를 가진다.

최대 K 무게를 가방에 넣을 수 있다고 할 때, 포함한 물건의 가치 V 합의 최대를 구해야한다.

 

3학년 학기 중에 풀어보았지만 가물가물해서  이 외국 유튜버의 풀이 가 상당히 유익했기에 다시 한 번 참고했다.

 

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

 

💭 풀이 과정

 

 

dp[i][j] = max(dp[i-1][j] , dp[i][j-index] + value)  의 점화식을 가진다.

 

 

1. 가방 공간보다 이 물건의 무게(product[i][1]) 이 더 클 때는 포함하지 못하므로 이를 제외한 무게로 대체한다.

 

2. 가방 공간보다 이 물건의 무게(product[i][1]) 이 더 작을 때는 포함 할 수도, 포함하지 않을 수도 있으므로 두 경우를 모두 따져보아 더 큰 값으로 대체한다.

 

 

 

 

작성 언어: C++

 

#include <cstdio>
#include <algorithm>    // std::max

int dp[101][100001] = {0, };    // 0-1 knapsack problem DP 배열
int product[101][3] = {0, };    // 1열은 물건의 무게, 2열은 물건의 가치

int main(){
    int sackCnt, sackWeight;
    scanf("%d %d", &sackCnt, &sackWeight);
    
    // 입력으로 주어진 배낭의 물품 수, 배낭의 최대 무게
    for (int i = 1; i <= sackCnt; ++i) {
        scanf("%d %d", &product[i][1], &product[i][2]);
    }
    
    for (int i = 1; i <= sackCnt; ++i) {
        for (int j = 0; j <= sackWeight; ++j) {
            /* #1# 가방 공간보다 이 물건의 무게(product[i][1]) 이 더 클 때는 포함하지 못하므로
                   이를 제외한 무게로 대체한다.
               #2# 가방 공간보다 이 물건의 무게(product[i][1]) 이 더 작을 때는 포함 할 수도, 포함하지 않을 수도 있으므로
                   두 경우를 모두 따져보아 더 큰 값으로 대체한다. */
            if (j < product[i][1]) {
                dp[i][j] = dp[i-1][j];
            }else {
                int minusIdx = j - product[i][1];  // 이 물건을 포함했을 때, 가방의 남은 무게
                dp[i][j] = std::max(dp[i-1][j], dp[i][minusIdx] + product[i][2]); // 이 물건을 포함하기 전과 포함한 후 중 더 가치가 큰 것을 선택
            }
        }
    }
    
    printf("%d\n", dp[sackCnt][sackWeight]);
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

0-1 knapsack problem 이라는 유명한 문제를 학기 중에 풀었었는데 다시 풀어서 맞추니 상당히 뿌듯했다 :D

 

계속해서 풀다보면 이런 경험이 더욱 쌓이겠지..!