[dp, knapsack] 2가지 다른 풀이

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

12865번: 평범한 배낭

dp[i] := i가치를 얻을 수 있는 최소 무게 O(N²V)

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define INF 100000000 // 100,000 x 100 보다 큰거
#define MAX 100000 // 1000 x 100
 
using namespace std;
typedef pair<int, int> pi;
 
int sol(vector<int>& dp, int K)
{
    for(int v = MAX; v >= 0; v--){
        if(dp[v] <= K) return v;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int N, K; cin >> N >> K;
    vector<pi> vec(N); // {weight, val}
    for(auto& [weight, val]: vec) cin >> weight >> val;
 
    vector<int> dp(MAX+1, INF); // i가치를 얻을 수 있는 최소 무게
    dp[0] = 0;
    for(int i = 0; i < N; i++){
        auto [weight, val] = vec[i];
        for(int v = MAX; v >= val; v--){
            dp[v] = min(dp[v], dp[v-val]+weight);
        }
    }
 
    cout << sol(dp, K) << endl;
 
    return 0;
}cs

 

dp[i] := i무게로 얻을 수 있는 최대 가치 O(NK)

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
 
using namespace std;
typedef pair<int, int> pi;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int N, K; cin >> N >> K;
    vector<pi> vec(N); // {weight, value}
    for(auto&[weight, val]: vec) cin >> weight >> val;
 
    vector<int> dp(K+1, 0);
    for(int i = 0; i < N; i++){
        auto& [weight, val] = vec[i];
        for(int w = K; w >= weight; w--){ // 갱신순서 큰거에서 작은 순으로 해야 됨
            dp[w] = max(dp[w], dp[w-weight]+val);
        }
    }
 
    cout << dp[K] << endl;
 
    return 0;
}cs