백준 12865(평범한 배낭)[C/C++]

🔗링크

1. 문제 풀이

이 문제는 가장 기본적으로 알려진 DP문제인 냅색(Knapsack)문제이다.
DP문제의 핵심은 어떠한 문제를 작은 부분 문제들로 나누어 푸는 것으로
작은 부분 문제들의 답들을 기억하고 이를 활용해 큰 문제의 답을 구하면 된다.

그림과 함께 설명하겠다.

---

이러한 경우를 가정하였을 때

---

물건을 선택시 만들수 있는 경우의 수들을 저장하기 위해 1~6kg까지의 가방들로 나누고
첫번째 물건을 가능한 모든 가방에 넣어본다.

---

그 다음 2번째 물건 차례에선 이전의 가방들을 이용해 더 효율적인 가방을 만들어낸다.

위의 경우에서 가방4~6번의 경우 중 4번만 자세히 보자면

가방4는 4kg을 수용할 수 있기에 2번째 물건을 넣게 되어도 (4 - 1)kg인 3kg의 공간이 남게 된다.
그렇기에 남은 3kg공간엔 우리가 이전에 만들어둔 가방3을 넣을 수 있다!!

결국 이 문제는

가방[n] = MAX(가방[n], 가방[n - m] + 물건A의 가치)
(m은 현재 물건의 무게)

다시 쓰자면

dp[n] = MAX(dp[n], dp[n - m] + value)
이 공식으로 풀이가 가능하게 된다.

---

위의 방식과 동일하게 순차적으로 모든 물건들을 처리한다면

결국 최종 답을 구해낼 수 있다.

2. 코드

#include <stdio.h>

int dp[100001], N, K, w, v;

int main() {
    scanf("%d %d", &N, &K);
    for (int i = 0;i < N;i++) {
        scanf("%d %d", &w, &v);
        for(int j = K - w;j >= 0;j--)
            if (dp[j + w] <= dp[j] + v)
                dp[j + w] = dp[j] + v;
    }
    printf("%d",dp[K]);
    return 0;
}

3. 후기

유명한 문제니까 항상 복습하자!!
(그리고 설명 좀 더 잘하도록,,)