[BOJ] 12865. 평범한 배낭 - c++

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

dp 풀이

dp[i][w]=물건 1~i까지만 고려하고 임시 배낭 용량이 w일 때의 최대 가치
1.물건 i를 배낭에 담지 않는 경우, dp[i,w]=dp[i-1,w]

2.물건 i를 배낭에 담는 경우, 현재 무게인 w에서 물건 i의 무게인 weight[i]를 뺀 상태에서 물건을 (i-1)까지 고려했을 때의 최대 가치인 dp[i-1]w-weight[i]]와 물건 i의 가치 value[i]의 합이 dp[i,w]가 된다.

#include <iostream>
int weight[101];
int value[101];
int dp[101][100001];
using namespace std;
int N,K;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> K;
    for(int i=1;i<=N;i++){
        cin>>weight[i]>>value[i];
    }
    for(int i=1;i<=N;i++){
        for(int w=1;w<=K;w++){
            if(weight[i]>w) // 물건i의 무게가 임시 배낭의 용량을 초과하면
                dp[i][w]=(dp[i-1][w]);
            else//물건 i를 배낭에 담지 않을 경우와 담을 경우 고려 
                dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight[i]]+value[i]);
        }
    }
    cout<< dp[N][K];
}