백준 12865 평범한 배낭 c++ [컴공과고씨]

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

12865번: 평범한 배낭

이 문제같은 경우 다이나믹 프로그래밍에 대표적인 문제라고 할 수 있다.

각 경우에 대해서 최선의 선택을 하면서 가면 되는데 이 말을 이해하기 위해서는 직접해보는 것이 좋다.

표를 다 채운 결과

표를 직접 그려봤다면 이게 무슨 원리인지 알 것이다. 자신이 채우고 있는 행의 최선의 선택은 

1. dp[i][j] = dp[i][j-현재 물건 무게] + 현재 물건 가치 이다.

2. dp[i][j] = dp[i-1][j] or dp[i][j-1] 둘 중 큰 값

 

1,2번중에서 큰 값을 선택해주면 최선의 선택이 된다.

 

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[102][100002] = {0};
 
int mx(int a, int b){
    return a > b ? a : b;
}
bool cmp(pair<int, int> p1, pair<int, int> p2){
    return p1.first < p2.first;
}
int main(){
    vector<pair<int, int>> wv;    
    int n, k, w, v;
    cin >> n >> k;
    wv.push_back(make_pair(0, 0));
    for (int i = 0; i < n;i++){
        cin >> w >> v;
        wv.push_back(make_pair(w, v));
    }
    sort(wv.begin(), wv.end(), cmp); //무게 기준 정렬
 
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k;j++){
            if(j-wv[i].first >=0){ 
            // j-물건 무게가 음수이면 물건을 넣지 못함.
                dp[i][j] = dp[i - 1][j - wv[i].first] + wv[i].second;
            }
            if(mx(dp[i-1][j], dp[i][j-1]) > dp[i][j]){
                dp[i][j] = mx(dp[i - 1][j], dp[i][j - 1]);
                //바로 직전 값과 위의 행 값을 비교              
            }
        }
    }
    cout << dp[n][k];
    return 0;
}

체감난이도	걸린시간	참고	사용 알고리즘
중	26min	x	dynamic programming 다이나믹 프로그래밍