[BOJ 12865] 평범한 배낭

문제 출저 : https://www.acmicpc.net/problem/12865

 

풀이 :

 

DP문제입니다.

무게와 물건의 2차원 공간에 Memoization을 적용하여 DP로 풀면 됩니다.

데이터를 쌓을 때 이전 까지 쌓아온 값과

이전 까지 쌓아온 값 중 현재 들어온 물건의 무게(w)를 뺀 후 가치(v)를 더한 값을 비교하여 큰것을 취득합니다.

한마디로 cache[i][j] = Max(v + cache[i - 1][j - w], cache[i - 1][j]) 가 됩니다.

저는 삼항연산자를 좋아하는 편이라 코드에는 Max대신 삼항연산자가 들어있습니다.

 

#include<stdio.h>
 
int n,k,Max,cache[100][100001],v,w;
 
int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &w, &v);
        if (i == 0)for (int j = w; j <= k; j++)cache[0][j] = v;
        else for (int j = 0; j <= k; j++)
        {
            if(j>=w)cache[i][j] = v + cache[i - 1][j - w] > cache[i - 1][j] ? v + cache[i - 1][j - w] : cache[i - 1][j];
            else cache[i][j] = cache[i - 1][j];
        }
    }
    printf("%d", cache[n - 1][k]);
}