[백준] 12865번 평범한 배낭

문제 제목처럼 평범한 Knapsack 문제 입니다. 

하지만, 너무 간만에 봐서 다 까먹고 쉽게 풀지 못한 문제이기도 합니다...ㅠㅠ

backtracking으로 풀어도 봤습니다. dfs로 재귀방식으로 모든 경우를 따져봤지만 역시나 시간초과가 뜹니다.

 

결국 DP로 풀어야 하는 문제입니다!

DP 변수의 각 index(물건) 마다 0~k까지의 무게에 대해 최대값을 넣어주면 됩니다.

 

2가지 경우로 나눠서 풀어주기만 하면 간단합니다.

1) i 번째 물건을 안넣는 경우

2) i 번째 물건을 넣는 경우

 

1번의 경우는 그냥 i-1의 무게를 유지해주면 되는 문제고,

2번의 경우는 현재 무게( j ) - 넣고자 하는 물건의 무게에 해당하는 v값을 더해주면 됩니다.

대신 넣을 때는 주의해야 할것이, 넣는 것이 오히려 안넣을 때보다 값이 낮을 수 있으니 비교해서 넣어주면 끝입니다.

 

아래는 구현한 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> d(n+1, vector<int>(k + 1)); // d[n+1][k+1]
    vector<pair<int, int>> item(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> item[i].first >> item[i].second;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            d[i][j] = d[i - 1][j];
            if(j-item[i].first >= 0)
                d[i][j] = max(d[i][j], d[i - 1][j - item[i].first] + item[i].second);
        }
    }
    cout << d[n][k];
    return 0;
}