白俊#12865.平凡なリュック

整理する

正しいコード

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int N, K;
    int W[101];
    int V[101];
    int dp[101][100001];
    // dp 2차원 배열의 바깥쪽은 i번째 물건일 때, 안쪽은 버틸 수 있는 무게가 j일 때의 값을 저장한다.
    
    cin>>N>>K;
    for (int i=1; i<=N; i++) {
        cin>>W[i]>>V[i];
    }
    
    // default 값 설정. 0번째 물건은 존재하지 않으므로 0으로 초기화.
    for(int i=0; i<=K; i++) {
        dp[0][i] = 0;
    }
    // default 값 설정. 배낭의 용량이 0이면 아무것도 넣을 수 없으므로 0으로 초기화.
    for(int i=0; i<=N; i++) {
        dp[i][0] = 0;
    }
    // 배낭의 용량이 j라고 할 때, i번째 물건을 넣을 수 있을까?
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=K; j++) {
            if (j - W[i] < 0) {
                // i번째 물건의 무게가 j보다 커서 넣을 수 없을 때
                dp[i][j] = dp[i-1][j];
            }
            else {
                // 무게가 j보다 작다면 가능한 두 가지 case 중 최댓값을 넣어준다.
                // 1. i번째 물건을 넣지 않은 경우
                // 2. i번째 물건을 넣는 경우 (이때는, i-1번째까지 넣었을 때, 남은 용량이 W[i]만큼은 확보되어 있어야 한다.)
                dp[i][j] = max(dp[i-1][j], V[i] + dp[i-1][j-W[i]]);
            }
        }
    }
    
    cout<<dp[N][K]<<endl;
    return 0;
}