[BOJ] 12865_평범한 배낭

평범한 배낭

문제링크: https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

DP문제를 해결하는데 여기서 도움을 받았다.
https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C

 

 

 

넣을 물건의 무게를 w 가치를 v라 하자.
dp 테이블 좌표 y,x를 가방의 무게가 x일 때 y번째 물건을 넣을때라 하자.
그렇다면, dp[y][x]는 물건을 넣고 나머지 무게의 가치 최대값, x - v 의 값을 구한다.
즉, dp[y][x] = dp[index][x-v] + w가 된다.
index는 해당 무게의 최대값을 저장하고 있는 index이다.

예로 위 테이블에서 가방의 크기가 7일때 4번째 물건을 넣는다고 하자.
그렇다면, x - v = 3이므로 가방 크기가 3일 때 가치 최대값은 6, dp[7][4] = 6 + 12 = 18이다.

위 식을 코드로 하면 다음과 같다.

 

• 정답코드

    #include<iostream>
    #include<algorithm>
    using namespace std;
  
    #define bagsNum 103
    #define maxNum 100001
    #define w first
    #define v second
  
    pair<int, int> bag[bagsNum];
    int dp[bagsNum][maxNum];
  
    pair<int, int> maximum;
    int n, k;
  
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
  
        cin >> n >> k;
  
        for (int i = 1; i <= n; i++)
            cin >> bag[i].w >> bag[i].v;
  
        int maxDP = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j - bag[i].w < 0)
                    continue;
                dp[i][j] = dp[101][j-bag[i].w] + bag[i].v;
                dp[102][j] = max(dp[101][j], dp[i][j]);
            }
  
            for (int j = 1; j <= k; j++) {
                dp[101][j] = dp[102][j];
                maxDP = max(maxDP, dp[101][j]);
            }
        }
  
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                cout << dp[i][j] << ' ';
            }
            cout << endl;
        }
  
        cout << maxDP;
  
        return 0;
    }