[DP] 최대/최소 KnapSack

최대 냅색

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Node {
    int weight;
    int value;
};


int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    
    vector< vector<int> > dp(n + 1, vector<int>(k + 1, 0));
    
    vector<Node> sack(n + 1);
    
    for (int i = 1; i <= n; ++i) {
        cin >> sack[i].weight;
        cin >> sack[i].value;
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if ( sack[i].weight <= j ) {
                if ( sack[i].value + dp[i - 1][j - sack[i].weight] > dp[i - 1][j] ) {
                    dp[i][j] = sack[i].value + dp[i - 1][j - sack[i].weight];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    cout << dp[n][k];
    
    return 0;
}

j - sack[i].weight는 현재 물건을 포함하고 남을 용량

=> 해당 용량 기준으로 생각하고 무게 구해야 함

---

 

최소 냅색

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define LARGE 2000000000

struct App {
    int mem;
    int cost;
};

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int totalMem = 0;
    int n, m;
    cin >> n >> m;
    
    App app[n + 1];
    
    
    for (int i = 1; i <= n; ++i) {
        cin >> app[i].mem;
        totalMem += app[i].mem;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> app[i].cost;
    }
    
    vector<int> dp( totalMem + 1, LARGE );
    dp[0] = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = totalMem; j >= app[i].mem; --j) {
            dp[j] = min( dp[j], dp[j - app[i].mem] + app[i].cost);
        }
    }
    
    int result = LARGE;
    for (int i = m; i <= totalMem; ++i) {
        result = min(dp[i], result);
    }
    
    cout << result;
    
    return 0;
}

최소 구하려면 전체 용량에서부터 뒤에서 접근해야 함