백준 12865번 - 평범한 배낭

가치합의 최댓값을 구하는 문제이다. 흔히 배낭 문제라고 하는데, 밑은 이 배낭 문제의 알고리즘을 잘 설명해놓은 글이므로 참고해서 어떻게 구현할 지 생각해보면 좋을 것 같다. (출처:huiyu's blog)

https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C

[DP] 0/1 Knapsack(배낭) 문제

예제 입력 1을 보면 4개의 물건과 최대 무게와 각 물건의 가치를 입력받는다. 좀 더 구체적으로 알고리즘이 어떻게 되는 지를 알기 위해서 최대 무게를 9라고 하자.

	1	2	3	4	5	6	7	8	9
6 (13)	0	0	0	0	0	13	13	13	13
4 (8)	0	0	0	8	8	13	13	13	13
3 (6)	0	0	6	8	8	13	14	14	19
5 (12)	0	0	6	8	12	13	14	18	20

일단 탐색을 할 때 마다 탐색하는 값과 최대 무게와의 차이를 구하고, 차이가 0보다 작으면 이전 값을 그대로 물려받고, 0보다 크면 값을 갱신해주면 된다. 5에 대해 탐색중일 때 최대 무게가 8인 경우(노란색)를 보면, 8과 5의 차이는 0보다 크고, 차이가 3이나 남기 때문에, 최대 무게가 3인 경우의 최대 가치합(연두색)과 5의 가치(청록색)의 합을 이전 값의 가치합(보라색)과 비교해줘서 큰 것으로 저장해주면 된다. 

##변수 선언 부분##
dp = []
stuff = []
value = []
max_sum = []
##메인 함수 부분##
if __name__ == "__main__":
    N, K = map(int, input().split())
    for i in range(N):
        s, v = map(int, input().split())
        stuff.append(s)
        value.append(v)
    max_sum = [[0]*(K+1) for x in range(N)]

    for i in range(K+1): #max_sum의 첫번째 값 설정
        if i - stuff[0] < 0:
            max_sum[0][i] = 0
        else:
            max_sum[0][i] = value[0]

    for i in range(1,N):
        for j in range(K+1):
            if j - stuff[i] < 0: #가방에 들어갈 자리가 없으면
                max_sum[i][j] = max_sum[i - 1][j] #값 갱신
            else: #들어갈 자리가 있고
                if max_sum[i-1][j] < (value[i]+max_sum[i-1][j-stuff[i]]): #이전 배열에서, 현재 탐색하는 수와 K의 차이만큼일 때 최대 이윤 값과 비교
                    max_sum[i][j] = value[i]+max_sum[i-1][j-stuff[i]]
                else:
                    max_sum[i][j] = max_sum[i-1][j]


    print(max_sum[-1][-1])

DP문제는 풀 때마다 어렵지만, 막상 푸는 법을 알면 코드를 짜는 것은 쉽다. 각 문제의 유형을 보고 어떤 식으로 코드를 짜야 할 지를 생각해야겠다.