12865 평범한 배낭

12865 평범한 배낭 (c++)

문제

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

접근 방식

Knapsack Problem, DP
쪼개질 수 없는 배낭 문제

문제 풀이

#include <cstdio>
using namespace std;
int main()
{
    int N, K, i, j, w, v; scanf("%d %d", &N, &K);
    int dp[K + 1] = {};
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d %d", &w, &v);
        for (int j = K; j >= w; --j)
        {
            if (v + dp[j - w] > dp[j]) dp[j] = v + dp[j - w];
        }
    }
    printf("%d\n", dp[K]);
}

다시 생각해 볼 점

1. 배낭문제는
   1. 쪼개지면 그리디
   2. 쪼개지지 않으면 DP
2. dp를 한줄로 최적화가 가능하다.