평범한 배낭 백준 - 12865번

이 문제는 knapsack유형의 문제라고 한다. 나는 이 문제를 처음 봤지만, 풀는데에 구글링을 해서 솔루션을 보았기에, 앞으로 dp유형과 knapsack유형이 익숙해질때까지 많이 풀고자 한다.

문제 설명

 

어느 dp문제가 그렇듯이, 점화식을 작성해야 한다. 처음 이 문제를 접했을 때, 기준점을 잡기가 어려웠다. 하지만, 구글링을 하게 된 결과, 기준은 내가 정하게 되는거란 것을 알게 되었다. 나는 기준을 입력순대로 정하였다. 

 

이 기준대로, 물건의 종류를 처음에는1개에서 2개, ....... n개까지 1개씩 증가시키면서 그때마다의 최댓값을 얻어냈다. 

1개일 때의 최댓값을 구하는건 쉽다. 무게보다 낮을경우 0, 높을 경우 해당 물건의 무게값.

k개일 때의 최댓값은 k-1개일 때의 최댓값에서 k번째 물건을 추가시킨 경우의 최댓값이다.

k+1개일 때의 최댓값 역시 k개일 때의 최댓값에서 k+1번째 물건을 추가시킨 경우의 최댓값일 것이다.

 

좀더 쉽게 풀기위해, 이렇게 쓰고보니, 수학적 귀납법의 꼴이 완성 되어 있었다.

그렇게 하여, 문제를 풀게 되었다.

#import<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
#define pii pair<int,int>
#define ff first
#define ss second

int n,k;
vector<vector<int>> dp(102,vector<int>(100003));
vector<pii> v(102);

void solve(){
    cin>>n>>k;
   rep(i,n){
        cin>>v[i].ff;
        cin>>v[i].ss;
    }
    for(int i =0;i<n;i++){
        int weight = v[i].ff;
        int value = v[i].ss;
        for(int j =0;j<=k;j++){
            if(i>0) {
                if(j<weight) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value);
            }
            else {
                if(j<weight) dp[i][j] =0;
                else dp[i][j] = value;
            }
        }
    }
    cout<<dp[n-1][k];
}
int main() {
    fast_io;
    solve();
    return 0;
}

www.acmicpc.net/problem/12865