[C++] 백준 - 12865 : 평범한 배낭

문제 링크

12865번: 평범한 배낭

 

풀이 )

  물건의 개수와 버틸 수 있는 무게에 대한 2차원 배열을 만들고 난 뒤

  물건을 넣지 않은 경우의 값과 넣었을 때의 값을 비교하여 최댓값을 저장한다.  

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[102][100002];

int main(void)
{
    int n, k, w[102], v[102];

    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", w+i, v+i);

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= k; ++j){
            memo[i][j] = memo[i-1][j];
            if(j >= w[i])
                memo[i][j] = max(memo[i][j], memo[i-1][j-w[i]]+v[i]);
        }
    }
    printf("%d\n", memo[n][k]);

    return 0;
}