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

12865 평범한 배낭

접근방법

현대 오토에버 코딩 테스트 준비 대비 문제로 푼 문제이다.  원래는 c 스타일의 코드를 c++의 문법으로 풀었는데, 코딩 테스트는 c로 풀어야해서 c++로 푼걸 다시 c로 변환 해봤다.

 

다이나믹 프로그래밍의 대표적인 문제인 배낭 문제로 배낭 문제란 제한된 무게를 가진 가방에 물건을 담을때 가치의 합을 최대로 넣는 방법을 찾는 문제이다.

다이나믹 프로그래밍의 특징은 문제를 작은 하위 문제로 만들수 있고, 이러한 동일한 하위 문제가 반복된다는 것이다.

다르게 말하면 기억하며 풀기라고도 말할 수 있다. 

이는 특정 문제에서 모든 조합을 계산하는 브루트포스 알고리즘보다 시간을 효율적이게 쓸수있다.

만약 i번째 물건까지 고려했을 때 , 무게가 w일때의 최대 가치는 dp[i][w]라고 가정하면, 초기 조건 dp[0][w] = 0 이다. 

만약 가져가지 않으면 dp[i][w] = dp[i-1][w] 이다. 가져가지 않았으므로 전에 i-1번째 물건의 최대가치와 비슷하기때문이다.

가져간다면 dp[i][w] = dp[i-1][w-W[i]] + value 이다  가져갈때 가져가는 물건의 무게만큼 빼고 가치는 더하면 된다.

이걸 반복하면 배낭 문제는 완료다. 다이나믹 프로그래밍은 구현은 쉽지만 구상이 어려운것 같다.

 

배낭 문제라고 했지만 이걸로 푸는 문제 종류 제한된 상자,시간 등등 에 최대한 가치가 있는 활동을 찾는 것이다.

 

 

코드는 다음과 같다.

#include <stdio.h>

int n, k;
int dp[101][100010];    
int weight[101];    
int value[101];      

#define MAX(a,b) ((a) > (b) ? (a) : (b))

int main(){
    scanf("%d %d", &n, &k);

    for(int i=1; i<=n; i++){
        scanf("%d %d", &weight[i], &value[i]);
    }

    for(int i=1; i<=n; i++){
        for(int w=1; w<=k; w++){
            if(w >= weight[i]){
                int notTake = dp[i-1][w];
                int take    = dp[i-1][w - weight[i]] + value[i];
                dp[i][w] = MAX(notTake, take);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    printf("%d\n", dp[n][k]);
    return 0;
}