백준 12865 (평범한 배낭)

백준 12865 평범한 배낭

문제 링크

문제 링크 : https://www.acmicpc.net/problem/12865

들어가기에 앞서

동적 계획법(dynamic programming) 국룰 문제 0/1 knapsack 문제입니다. 0/1은 on/off라고 생각하면 편합니다. 빠르게 설명하자면, n개의 item이 주어집니다. 이 item은 각각 value를 지닙니다. knapsack이라는 이름에 걸맞게, 무게 제한이 있는 가방에 item value가 최대가 되도록 item을 담는 문제라고 할 수 있습니다.

문제 접근

문제의 핵심은 최대가 되도록, item을 담는 것입니다. 즉, 최적화 문제라고 할 수가 있습니다.

그냥, 제일 value 높은 item들만 담으면 안 되는 것인가요? 당연히 안됩니다. 왜냐하면 무게와 가치를 다 따져야 하기 때문입니다. 가성비를 잘 따져봐야 한다는 것입니다. 즉 탐욕스럽게 해결할 수 없는 문제입니다.

예시로, 무게 10000 가치 20인 item이 1개, (무게 1 가치 1)인 item이 10000개 있다고 가정해봅시다. 나의 가방 무게 제한은 10000이라고 해보겠습니다. 당연히 2번 item을 10000개 담는 것이 정답이 됩니다. 탐욕법으로 해결할 수 없다고 확정이 났습니다.

만약 item을 분할할 수 있다고 생각해보겠습니다. 이러한 경우는 탐욕적으로 해결할 수 있게 되겠네요. 이러한 문제를 fraction with knapsack problem이라고 부릅니다. 아무튼 지금 상황에선 item을 분할하기 불가능하므로, 탐욕적으로 해결할 수 없습니다.

그렇다면 어떻게 해야 하는지 의문이 듭니다. 일단, 마땅한 아이디어가 없으니 완전탐색을 생각해봅시다. 완전탐색으로 n개의 물건에 대해 on/off (0/1)을 다 판단해보면 될 듯 합니다. 완전탐색 알고리즘의 시간 복잡도는 O(2^n)이 될 듯 합니다. n이 25보다 작은 수라면 고려해볼법 하지만, 실전에서 써먹기는 매우 힘들 것 같습니다.

이러한 이유로, 동적 계획법(DP)를 한 번 적용해보자는 것입니다. 그에 앞서, 최적의 해는 부분 최적의 해들의 집합으로 이루어진 명제가 0/1 knapsack problem에는 적용이 됩니다.
왜나고요?? 아!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 당연히 부분이 최적이어야!!!!! 그렇게 될 것 아닙니까!!!!!!!

죄송합니다. 한 번 그라데이션 분노를 적용해보고 싶었습니다. 배낭의 일부가 최적인 조건이 아니라면, 전체도 최적이지 않을 것임은 자명합니다. 이 명제에 대우를 적용한 결과라고 설명할 수 있겠습니다.

아무튼 동적 계획법으로 문제를 해결해보도록 해봅시다. 그에 앞서, 문제가 어떤 state로 정의가 되는지부터 생각을 해봅시다. 현재 가방에 들어있는 item의 무게와, 현재 item을 어떻게 넣었는지에 따라서, 현재 가방에 들어있는 item의 value가 결정됩니다. 따라서, 가방에 들어있는 item들의 무게와, item의 상태에 따라, 현재 state가 정의가 됩니다.

아! 그렇다면 이 2가지 특징으로 동적 계획법을 적용하기 위한 점화식을 세워보도록 하겠습니다. dp[i][j]를 1~i번째 item까지 고려한 상황 + 가방의 현재 최대 용량을 j라고 하면,

dp[i][j] = max(dp[i-1][j] , dp[i-1][j-now_item_weight] + now_item_value)라고 할 수 있습니다.

dp[i-1][j]는 내가 i번째 item을 넣지 않고, i-1번째 item까지 고려한다는 의미이고, dp[i-1][j-now_item_weight]는, 현재 item (i번째 item)을 넣는 경우를 고려하는데, i-1번째 item까지 고려한 경우에서, 현재 item을 넣을 수 있는 최대의 경우를 의미합니다.

12865번의 test case1번에 대한 dp table입니다.

이해가 되지 않는 내용이 있다면, 댓글로 달아주시길 바랍니다.

소스 코드

import sys

n,k=map(int,sys.stdin.readline().split()) #물건 수, 제한
dp=[[0 for _ in range(k+1)] for _ in range(n+1)]
answer=0
for i in range(1,n+1) :
    w,v = map(int,sys.stdin.readline().split()) #weight, value
    for j in range(1,k+1) :
        if j>=w :
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else :
            dp[i][j] = dp[i-1][j]

print(dp[n][k])   

마무리하며

다음은 dp 국룰문제 2번 traveling salesman problem (tsp)에 다뤄보도록 하겠습니다.