Algorithm/Dynamic Programming

[Baekjoon 12865 / python / 골드5] 평범한 배낭

양선규 2024. 4. 7. 23:34
728x90
반응형
import sys

N, K = map(int, input().split())  # 물건 수, 버틸 수 있는 무게
item = [[]]  # 물건 입력받기 (무게, 가치)
for _ in range(N):
    item.append(list(map(int, input().split())))

dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]  # dp테이블 만들기, 0행과 0열은 0으로 채우기

for x in range(1, K + 1):
    for y in range(1, N + 1):
        if x - item[y][0] >= 0:  # 현재무게 - 현재물건무게 값이 0이상이라면 (dp테이블에 있다면, 담을 수 있다면)
            dp[x][y] = max(dp[x][y-1], dp[x-item[y][0]][y-1] + item[y][1])  # 왼쪽값, 현재무게-현재물건무게값을 x행으로 한 왼쪽값중 큰 값 선택
        else: # dp테이블에 없다면, 담을 수 없다면
            dp[x][y] = dp[x][y-1]  # 왼쪽 값 선택

print(dp[-1][-1])

 

Knapsack Problem 이라고 불리는 DP의 대표적인 문제이다. 무게제한이 정해진 가방에 물건들을 담되 가치가 가장 높아지도록 담아야 한다. 물건마다 무게와 가치가 다르다.

 

이 문제도 여타 DP 문제처럼 점화식을 알아내면 쉽게 풀 수 있다. 다만 점화식을 알아내는게 매우 어렵다.

DP 테이블

 

평범한 배낭 문제에 제시된 예제의 답을 구하는 DP테이블이다. 물건은 열(y)값으로 선택되고 무게는 행(x)값으로 선택된다.

즉 6,13 4, 8 3,6 이것들이 물건이며 (무게, 가치) 형태이다.

또한 첫 번째 값부터 점화식을 적용하기 위해, 0행과 0열은 모두 0으로 채워둬야 한다.

 

점화식은 이렇게 된다.

if x-yk >= 0:

dp[x][y] = max(dp[x][y-1], dp[x-yk][y-1] + val)

else:

dp[x][y] = dp[x][y-1]

yk는 현재 선택된 물건의 무게를 의미한다.

 

즉 dp[x][y] 값은 dp[x][y-1] 로써 좌측 값이지만,

x - yk >= 0: 일 경우 ( 현재 선택된 무게 - 현재 선택된 물건의 무게 값이 0 이상 -> 해당 값이 dp테이블에 존재하며, 물건을 담을 수 있다는 뜻 )

dp[x-yk][y-1] + val 값과 dp[x][y-1]  값(좌측 값) 중에 더 큰 값을 선택한다.

dp[x-yk][y-1] + val은 [현재 선택된 무게 - 현재 선택된 물건의 무게][y-1] 를 의미한다.

 

처음 보면 엄청 헷갈릴 수 있는데, 표를 천천히 따라가며 점화식을 적용해보면 이해될 것이다.

물론 점화식을 스스로 알아내야 문제를 푼 것이겠지만.. 나처럼 DP를 이제 입문한 사람은 정 모르겠으면 답을 보고 이해한 후, 문제를 해결하는 능력과 시야를 키우는 것도 좋다고 생각한다.

728x90
반응형