[백준/Baekjoon] 12865 평범한 배낭 C++ :: Dynamic Programming

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

12865번: 평범한 배낭

1. Logic

- 버틸수 있는 무게 >= 지금까지의 무게 + 이번(넣을 or 넣지 않을) 차례의 무게

- 가능하다면 이후의 항의 최댓값에 현재 배낭의 value를 더해주기

 

#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int>> goods;
int dp[101][100001];
int n, k;

int solve(int weight, int cnt) {
    if(cnt == n) return 0;
    int &ret = dp[cnt][weight];
    if(ret != -1) return ret;
    ret = 0;
    //ret 가치 최댓값 / 무게 합 / 몇번 상품

    if(goods[cnt].first + weight <= k) {
        ret = max(ret, solve(weight + goods[cnt].first, cnt + 1) + goods[cnt].second);
    }
    ret = max(ret, solve(weight, cnt + 1));

    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        goods.push_back({w, v});
    }

    cout << solve(0, 0);
}

 

2. Feedback

dp테이블의 값과 solve 함수의 리턴값, 함수의 인자로 넘겨줘야 하는 값을 잘 확인하기