12865번 평범한 배낭(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.

백준) 평범한 배낭(12865번)

평범한 배낭

문제 설명: 최대 k 무게만큼 넣을 수 있는 배낭에 가치를 넣을 수 있는 최대값을 구하시오.

문제 설명

문제에서 물품의 수(N)는 최대 100 입니다.
물건 각각에 대하여 물건을 배낭에 넣을지 말지, 모든 경우를 수행한다면, 이 방법의 시간복잡도는 다음과 같습니다.

Brute-Force 방법 시간복잡도: O(2^100)

하지만 이 방법으로는 시간안에 문제를 풀 수 없으므로 다이내믹프로그래밍 방법으로 문제를 풀어봅시다.

d[i][j]를 i번째 물건까지 고려하였을때, j 무게를 넣은 경우의 가치 최대값이라고 정의하여 봅시다.

d[i][j]를 다음과 같이 표현이 가능합니다. 이 방법의 시간 복잡도는 물건의 수(N), 최대무게(K)에 대하여 다음과 같습니다.

DP 시간복잡도: O(N*K)
d[i(물건)][j(무게)]=(최대 가치)
i번째 물건을 넣지 않을 때, d[i][j]=d[i-1][j]
i번째 물건을 넣을 때, d[i][j]=d[i-1][j-w[i]]+v[i]
따라서, d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+v[i])

위의 점화식의 정의에 따라 Bottom-Up 방식으로 코드를 구현하여 보겠습니다.

구현 과정

d = [[0] * (k+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(1,k+1):
    d[i][j]=d[i-1][j]
    if j-w[i]>=0:
      d[i][j]=max(d[i][j], d[i-1][j-w[i]]+v[i])
print(d[n][k])

Kanpsack algorithm으로 널리알려진 문제입니다.
DP를 배울때 교과서적인 예시로 나오는 문제이므로 익혀두도록 합시다.

전체 구현 코드

import sys
def input(): return sys.stdin.readline().rstrip()

n,k = map(int,input().split())
temp = [list(map(int,input().split())) for _ in range(n)]
w,v = zip(*temp)
w = [0] + list(w)
v = [0] + list(v)
d = [[0] * (k+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, k+1):
        d[i][j] = d[i-1][j]
        if j-w[i] >= 0:
            d[i][j] = max(d[i][j],d[i-1][j-w[i]]+v[i])
print(d[n][k])