[BOJ 12865] 평범한 배낭

1) 문제 링크

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

2) 접근

Knapsack 문제가 떠올랐다. 근데 구현은 잘 생각 안 나서 애먹었다…

3) 풀이

#include <iostream>
using namespace std;
const int MAX = 100;
const int MAX_WEIGHT = 100001;

int N, K;
int dp[MAX][MAX_WEIGHT], W[MAX], V[MAX];

// n번째 물건부터 사용해서 무게 w을 채웠을 때 가치의 최댓값
int backpack(int n, int w){
    if(n == N) { return 0; } // base case: 모든 물건을 검토한 경우
    if(dp[n][w] != -1) { return dp[n][w]; }

    int result;
    if(w < W[n]) { result = backpack(n+1, w); }
    else { result = max(backpack(n+1, w), backpack(n+1, w-W[n])+V[n]); }
    dp[n][w] = result;

    return result;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> K;
    for(int i=0; i<N; ++i){
        cin >> W[i] >> V[i];
    }

    // fill dp array
    for(int i=0; i<MAX; ++i){
        for(int j=0; j<MAX_WEIGHT; ++j){
            dp[i][j] = -1;
        }
    }

    cout << backpack(0, K);

    return 0;
}

4) 피드백

딱히 없다.