https://www.acmicpc.net/problem/12865
아주 평범한 배낭에 대한 문제다.
문제의 내용은 간단하다. 곧 군대를 가는 준서🥲를 위해 가방이 찢어지지 않으면서 가장 큰 가치가 담기도록 가방을 싸주면 된다.
멋진 말로 "배낭에 넣을 수 있는 물건들의 가치 합의 최댓값"을 구해주는 문제이다.
전형적인 동적 프로그래밍(Dynamic Programming) 문제라고 하는데, 사실 DP를 처음 마주하는 입장으로써는 이해하는 것도 쉽지 않았던 것 같다.
문제 접근 방법
-
가방이 담을 수 있는 최대 무게의 양을 1씩 늘려나가면서, 현재의 최대 무게에서 몇 개의 물건을 어떻게 담는 것이 최대 가치를 가지게 될까? 고민하며 물건을 담는다.
-
가방에 넣을 수 있는 물건의 개수를 하나씩 늘려나가면서 "이 물건을 넣는 것이 이익일까?(가방에 담을 수 있는 전체 가치가 늘어날까?)"를 고려하며 물건을 담는다.
- 이익이면 가방에 넣고
- 이익이 아니면 가방에 넣지 않는다.
점화식 세워보기
먼저 dp 배열을 다음과 같이 정의한다.
dp[item][max_weight]
- dp[item][max_weight]: 가방에 담을 수 있는 가치의 최대값
- item: 첫번째 물건부터 몇 번째 물건까지 가방에 담을 수 있음
- max_weight: 배낭에 담을 수 있는 최대 무게
가방에 담을 수 있는 최대 무게가 정해졌을 때, 담을 수 있는 최대 가치를 구한다.
가방에 담을 수 있는 최대 무게를 max_weight라고 할 때, 현재 내가 손에 들고 있는 무게가 weight인 물건에 대해 두 가지 액션을 취할 수 있다.
-
가방에 넣지 않는다.
이 때 가치의 최댓값은, 이전 물건까지를 담았을 때의 가치 최댓값과 같다.
dp[item-1][max_weight] -
가방에 넣는다.
이 물건을 가방에 넣는다면, 이 물건을 제외하고 가방에 담을 수 있는 물건 무게의 합은max_weight - weight이 된다.
가방에 담을 수 있는 가치의 최댓값은 현재 물건의 가치 +max_weight - weight까지 담을 수 있는 최대 가치이다.
dp[item-1][max_weight-weight]
따라서 현재의 무게에서 담을 수 있는 최대 가치는 둘 중에 큰 값이 된다!
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight]+value)
작성 코드
import sys
input = sys.stdin.readline
# 가방싸기 함수
def knapsack(N,K,items):
dp = [[0]*(K+1) for _ in range(N+1)]
# 가방에 담을 수 있는 물건의 개수를 1개부터 하나씩 늘려 나간다
for i in range(1,N+1): # i: item
weight, value = map(int, items[i-1])
# 가방에 담을 수 있는 최대 무게를 1부터 차례대로 증가시켜 나가면서
for j in range(1,K+1): # j:가방에 담을 수 있는 무게
# 현재 물건이 가방이 담을 수 있는 무게보다 작으면
if weight <= j:
# 현재 물건을 넣지 않았을 때와 현재 물건을 넣었을 때의 가치를 비교한다.
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight]+value)
# 크면 이 물건을 담지 않고 이전 물건까지 담았을 때 가방에 담을 수 있는 최고 가치를 저장
else:
dp[i][j] = dp[i-1][j]
# 가방에 담을 수 있는 최대 무게에서 모든 물건을 고려했을 때의 최대값을 출력
print(dp[N][K])
# N: 물건 개수 K:가방에 담을 수 있는 최대 무게
N, K = map(int, input().split())
# 각 물건의 무게와 가치
items = [list(map(int, input().split())) for _ in range(N)]
# 주어진 조건으로 가방싸기!
knapsack(N,K,items)더 나은 방법
dp 2차 배열 대신 1차 배열을 사용하는 방법도 있다고 한다!
참고한 블로그: 냅색 알고리즘
https://reakwon.tistory.com/34
