[12865번] 평범한 배낭

배낭(Knapsack) 문제 중 짐(item)을 쪼갤 수 없는 0-1 냅색 문제

DP(동적계획법)의 대표적 문제 중 하나

입력은 N(item의 개수), K(배낭의 최대 무게)와
각 item의 w(무게), v(가치)이다.

입력을 바탕으로 배낭에 넣은 물건의 가치의 합이 최대가 되도록 한다.

점화식을 세워보면 아래와 같이 나타낼 수 있다.

DP( i, w ) = | max( DP( i, w ) , DP[ w - item[i].weight ] + item[i].value ] ) ( item[i].weight <= w )

                | DP( i, w) ( item[i].weight > w )

( i : 현 아이템 번호, w : 현 배낭의 무게 )

여기서 w를 최대 K부터 1까지 줄여가면서 배낭을 채워나가고 현 아이템에 대해 기록이 끝났다면 다음 아이템으로 넘어가서 반복하도록 한다.

예시로,
4 7 // N K
6 13
4 8
3 6
5 12
란 입력이 들어오게 되면 아래와 같이 저장하고 DP(가방) 배열을 채워 나간다.

1번 item -> weight : 6 , value : 13

2번 item -> weight : 4 , value : 8

3번 item -> weight : 3 , value : 6

4번 item -> weight : 5 , value : 12

step 1) 1번 item

무게가 7인 가방을 1번 item만으로 채울 수 있는 최대 가치는 13

무게가 6인 가방을 1번 item만으로 채울 수 있는 최대 가치는 13 

무게가 5인 가방을 1번 item만으로 채울 수 있는 최대 가치는 0 ....

 

step 2) 2번 item

무게가 7인 가방을 2번 item과 1번 item으로 채울 수 있는 최대 가치는

step1의 7번 arr의 13 vs item_2의 가치 8 + 남은 무게(3)의 가치 0를 비교해서 최대 가치인 13을 저장

....

무게가 5인 가방을 2번 1번 item으로 채울 수 있는 최대 가치는

step1의 5번 arr의 0 vs item_2의 가치 8 + 남은 무게(1)의 가치  0을 비교해서 최대 가치인 8을 저장

 

이런식으로 DP배열을 채워나가면 최종적으로 DP[K]의 값이 내가 구할 답이된다.

 

각 step을 진행 할 때 마다 기록되는 숫자는 이전 item의 정보도 담고 있기 때문에 1차원 배열로 충분히 처리할 수 있다.

 

 

#include <stdio.h>
#include <algorithm>
using namespace std;
int N, K;
struct info { int weight, value; }item[105];
int DP[100005];
 
int main() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        int w, v;
        scanf("%d %d", &w, &v);
        item[i] = { w,v };
    }
 
    for (int I_idx = 1; I_idx <= N; I_idx++) {
        for (int w = K; w >= 1; w--) { // w : 현재 사용할 수 있는 배낭의 무게(공간)
            int tmp = DP[w - item[I_idx].weight]; //현재 아이템을 넣었을 때 남은 공간이 가지는 최대 가치
            DP[w] = item[I_idx].weight <= w ? max(DP[w], tmp + item[I_idx].value) : DP[w];
        }
    }
 
    printf("%d", DP[K]);
    return 0;
}