[백준/C++][평범한 배낭(12865번)]

문제

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

12865번: 평범한 배낭

문제 해결

1~K까지 물건을 하나씩 넣어보면서 만약 물건의 무게가 더 크다면 패스 무게가 더 적다면 i-1값과 현재 현재 물건 가치 + 남은 무게의 dp값(하나씩 갱신 하므로 이 dp의 값은 남은 무게의 최대값이다.) 을 비교해서 더 큰 값을 dp에 넣는다. 이 방법을 K까지 반복하게 된다면 마지막 K무게에서의 마지막 물건의 dp의 값이 곧 답이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair<int,int>> v;
int N,K;
int dp[101][100001] = {0,};
int main(void){
    cin >> N >> K;
    v.push_back({0,0});
    for(int i = 0;i<N;i++){
        int a,b;
        cin >> a >> b;
        v.push_back({a,b});
    }
    for(int i = 0;i<=K;i++){
        for(int j = 1;j<=N;j++){
            int weight = v[j].first;
            int price = v[j].second;
            if(weight>i){dp[j][i] = dp[j-1][i];}
            else{
                dp[j][i] = max(dp[j-1][i],dp[j-1][i-weight]+price);
            }
        }
    }
    cout << dp[N][K];
}