[BOJ 12865] 평범한 배낭

문제는 여기에서 확인할 수 있다.

---

간단하고 유명한 knapsack문제이다.

D[k][n]을 n번째 물건까지 보고, 배낭의 무게가 k일 때, 배낭의 물건의 가치의 합의 최대라고 놓으면 점화식은 D[k][n] = max(D[k-u[i]][i+1] + e[i])이다. (u는 물건의 무게, e는 가치)

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int lld;
 
lld s, n, u[105], e[105];
lld d[100001][105];
 
lld solve(int cap, int i) {
    if(i == n) return 0;
    lld &ret = d[cap][i];
    if(ret != -1) return ret;
    ret = solve(cap, i+1);
    if(cap >= u[i])
        ret = max(ret, solve(cap - u[i], i+1) + e[i]);
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    cin >> s; 
    vector<int> rst;
    for(int i = 0; i < n; i++)
        cin >> u[i] >> e[i];
    memset(d, -1, sizeof(d));
    cout << solve(s, 0) << endl;;
    return 0;
}