백준 12865번: 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

Solved By: Knapsack DP

 

처음으로 시도해본 Knapsack DP문제입니다. 이론을 공부하면서 코드를 써봤는데 아직 완전히 이해되지는 않았습니다.

각 아이템 당 무게와 가치는 pair형 배열을 선언하여 저장해주었습니다.

#include <iostream>
using namespace std;

int n, k;
int cache[101][100001]; // 물품의 최대 개수 = 100개, 준서가 버틸 수 있는 최대 무게 100000
pair<int, int> item[101];

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        // first == 무게, second = 가치
        cin >> item[i].first >> item[i].second;
    }
    
    for(int i = 1; i <= n; i++){ // 각 보석에 대하여
        for(int j = 1; j <= k; j++){ // 최대 제한 무게가 j이 일 때
            if(item[i].first <= j){
                // 현재 아이템 무게에 대하여 넣을 수 있을 때
                
                // 1) 넣지 않는다.
                // 전 아이템을 넣고, 무게 배낭 한도가 j였을 때의 최대 이익 값을 가져온다.
                // => cache[i - 1][j]
                
                // 2) 넣지 않은 것보다 현재 물건을 넣은 것이 더 좋은 경우
                // => item[i].second + cache[i - 1][j - item[i].first]
                // == 현재 아이템의 가치 + 이전까지 물건을 넣었고, 무게 한도가 j - weight(i)일 때
                cache[i][j] = max(cache[i - 1][j], item[i].second + cache[i - 1][j - item[i].first]);
            }
            else{
                cache[i][j] = cache[i - 1][j];
            }
        }
    }
    
    cout << cache[n][k];
    return 0;
}