백준 12865 평범한 배낭(c++)

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

12865번: 평범한 배낭

주어진 입력은 배낭의 무게(w)와 가치(v)입니다. 배낭의 수용량을 넘지 않으면서 가치의 최댓값을 구하는 문제입니다. 

점화식은 다음과 같이 세울 수 있습니다.

물건을 담지 않은 경우 D[i][j] = D[i-1][j]

물건을 담은 경우 D[i][j] = D[i-1][j-w[i]] + v[i]

물건을 담은 경우 에는 수용량과 가치 갱신해줘야 합니다. 

3행 7열을 기준으로 보면, D[i-1][j-w[i]](8) + v[i](6) = 14 > D[i-1][j] = 13 이므로 14로 갱신되었음을 확인할 수 있습니다.

 

<코드>

#include <iostream>

using namespace std;
// D[i][j] = i번째 물건 고려, 배낭에 넣은 물건 무게의 합이 j일 때, 가치의 최댓값
// 점화식 물건을 넣은 경우, D[i-1][j-w[i]] + v[i];
// j-w[i]>=0 -> d[i][j] = max(d[i][j], d[i-1][j-w[i]]+v[i]);
// 물건을 넣지 않은 경우, 변화 x : D[i-1][j]

int main()
{
    int d[101][100001];
    int v[101];
    int w[101];
    int n, k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>w[i]>>v[i];
    }
    d[0][0] = 0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=k;j++) {
            d[i][j] = d[i-1][j];
            if(j-w[i]>=0) {
                d[i][j] = max(d[i][j],d[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<d[n][k]<<'\n';
}