백준 12865 파이썬 _ 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

dojinkimm.github.io/algorithm/2019/10/19/dp-2.html

Study Blog

참고하시면 좋을것 같습니다!

 

문제유형 : DP

문제핵심 : 0부터 최대무게까지 돌면서 현재물건을 챙길때 vs 현재물건을 챙기지않을때 중 큰값으로 갱신(?) 

 

이 문제는 DP의 대표적인 문제 유형중 하나라고 한다.

 

배낭에 담을 수 있는 최대무게가 주어질때, 배낭에 담을 수 있는 최대가치를 구하는것이다.

이때 물건을 쪼갤수 없기때문에 물건을 담는다/안담는다 로만 나뉠수 있어서 0-1 knapsack problem이라고 부른다.

 

DP를 사용하면 문제를 작은단위의 문제 (sub-problem)으로 나누고, 각 sub-problem에 대한 최적답을 저장하는식으로 문제를 푼다.

 

값저장을 위해 이차원배열을 만드는데 배열의 인덱스는 각각 배낭이 견디는 무게 / 물품의 index를 의미한다.

예를들어 dp[2][2] 의 값은 내가담을수있는 무게가 최대2이고, 1번 2번 물건들중에서만 고를때의 최대가치를 의미한다.

따라서 최종적으로 dp[k][n]가 문제에서 요구하는 최대무게k일때 물건 n개중에서 골라 만들수있는 최대가치가 된다.

 

이차원배열 dp를 갱신하는 식은 다음과 같다.

출처 : https://dojinkimm.github.io/algorithm/2019/10/19/dp-2.html

위의식은 내가 넣을 수 있는 물품이 있는데, 그 물품의 무게가 최대무게를 초과하면 가치를 추가하지 않고 이전 가치를 그대로 가져온다는것이다.

밑에식은 나에게 새로운 물품이 있고 최대 무게를 넘어서지 않는다는 조건을 만족할때, 이전 가치 vs 이전것의 물품을 빼고 내가 새로 받은 물품의 가치를 넣었을때의 가치를 비교해서 더 큰것을 취한다는 것이다.

 

코드

import sys
input = sys.stdin.readline
n,k = map(int, input().split())
input_list = [ [] for _ in range(n)]

for i in range(n):
    a,b = map(int, input().split())
    input_list[i].append(a)
    input_list[i].append(b)

dp = [ [0 for _ in range(k+1)] for _ in range(n+1)] # k무게를 버틸수있는 n개의 물건으로 만들수있는 최대가치를 저장하는 2차원배열

# 가져갈수있는 물건 (외부반복) / 배낭의 최대무게 (내부반복)
# 무게가 0이거나 물건이 0개일때는 0이므로 1부터 시작
for i in range(1, n+1):
    for j in range(1, k+1):
        w = input_list[i-1][0]
        v = input_list[i-1][1]
        if w > j: #현재 물건의 무게가 최대무게를 초과하면 못가져감
            dp[i][j] = dp[i-1][j]
        # 현재물건의 무게가 최대무게보다 작으면 가져갈수는 있음
        # 단, 이걸 가져가는것(현재가치+지금물건빼고 나머지만 가지고서, 현재견딜수잇는 무게-지금챙기는 물건무게에서의 최대가치 vs 안가져가는것 중에 더좋은것을 채택해야함
        else:
            dp[i][j] = max(v + dp[i-1][j-w], dp[i-1][j])

print(dp[n][k])