[동적계획법/DP] 백준 12865 평범한 배낭 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

12865번: 평범한 배낭

 

 

 

2. 문제 풀이

 제한된 배낭 용량에 최대한 가치있는 물건들을 채우는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 그리디 알고리즘은 '동전 거스름돈', DP는 '배낭' 문제가 대표 예제로 손꼽힙니다.

 1~K까지의 무게별로 가치의 최대값을 기록한 뒤, 아이템을 하나씩 넣었을 때와 넣지 않았을 때를 가치 비교합니다.

 

 

cache[현재 무게] = max(cache[현재 무게], cache[현재 무게 - 물건의 무게] + 물건의 가치)

  배낭 문제의 점화식은 위와 같습니다. 넣을 물건의 무게만큼 뺀 다음에, 해당 물건을 넣은 가치와 비교합니다. 해당 물건의 무게만큼 다른 것들을 빼고 넣어도 가치가 높다면, 해당 물건을 넣습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())
item = []
for _ in range(N):
    item.append(list(map(int, input().split())))

# DP
cache = [0]*(K+1)

# 1부터 K까지 1씩 늘려가며 가치의 최댓값 구하기
for weight, value in item:
    for i in range(1, K + 1):
        # 베낭에 아이템을 넣을 수 있으면 비교 후 갱신
        if i >= weight:
            # 배낭에 해당 아이템을 넣는 게 유리하면 갱신
            cache[i] = max(cache[i], cache[i-weight] + value)
print(cache[K])

 단순히 cache를 물건 무게로만 하면, 가치가 높은 동일한 아이템을 계속 넣게 됩니다. 위 문제에서는 물건이 1개씩 밖에 없으므로, 1개로 제한해줘야 합니다.

 

 

import sys
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())
item = []
for _ in range(N):
    item.append(list(map(int, input().split())))

# DP
cache = [[0]*(K+1) for _ in range(N+1)]

# 아이템 하나씩 넣고 빼며 가치 비교
for idx, thing in enumerate(item, 1):
    weight, value = thing
    # 1부터 K까지 무게를 늘려가며 가치의 최댓값 구하기
    for i in range(1, K + 1):
        # 베낭에 아이템을 넣을 수 있으면 비교 후 갱신
        if i >= weight:
            # [해당 아이템 이전의 가치의 최댓값]과 [해당 아이템을 추가한 후의 가치] 비교
            cache[idx][i] = max(cache[idx-1][i], cache[idx-1][i-weight] + value)
        # 아이템을 추가할 수 없으면 이전 가치의 최댓값 그대로
        else:
            cache[idx][i] = cache[idx-1][i]
print(cache[N][K])

 따라서 cache를 (N+1) * (K+1) 크기로 사용합니다. 아이템을 한 가지씩 추가하면서, 최대 가치를 찾습니다.