Boj 12865 c++ 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

knapsack 문제 중 기본문제이다.

우선 이차원 dp배열은 i번째 물건까지 고려하였을 때, 용량이 K인 배낭에 담을 수 있는 가치의 최댓값으로 정의하였다.

점화식을 이해하는 것이 중요한 문제. 또한 dp문제를 풀이하는 경우에는 할 수 있는 시행의 종류를 생각해보아야 한다. 이문제의 경우에는 특정 물품을 넣을 공간이 있을 때와 없을 때가 구분된다.

만약 용량보다 물건의 무게가 크다면 dp배열의 값은 변동이 없다.

하지만 용량보다 작은 물건의 경우에는 그 물건을 넣지 않는 경우와 그 물건을 넣는 경우 두가지가 존재한다. 그 경우에는 둘 중 더 가치가 큰 선택을 한다. 

핵심은 1부터 최대용량 K까지의 용량 모두에 대한 dp배열 값을 모두 저장하는 것이다.

#include<iostream>
using namespace std;
int W[101], V[101];
int dp[101][100001]; //물건의 가치의 합
int main(){
    int N, K;
    cin>>N>>K;
    for(int i=1; i<=N; i++){
        cin>>W[i]>>V[i];
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<=K; j++){
            if(W[i]>j){
                dp[i][j]=dp[i-1][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j], V[i]+dp[i-1][j-W[i]]);
            }
        }
    }
    cout<<dp[N][K];

}