[백준] 12865번: 평범한 배낭

평범한 배낭문제는 배낭에 담을 수 있는 최대 무게가 정해져있고, 이 무게를 넘지 않고 물건의 가치의 합이 최대가 되도록 물건을 가방에 담는 문제다.

 

사실 굉장히 단순한 문제인데 이해하지 못하는 부분이 있어 풀이에 시간이 꽤 걸렸다.

 

이 문제는 dp(dynamic programming)로 풀 수 있는 문제이다.
dp는 큰 문제를 작은 문제로 나눠서 푸는 문제를 말한다. 
이를 위해서는 작은 문제가 반복되어야하고, 작은 문제의 최적의 결과를 이용해 큰 문제의 결과를 도출해낼 수 있어야한다.

 

여기서는 전체 배낭(최대 무게 k)에 전체 물건을 담을 수 있는 경우가 큰 문제에 해당하고,

몇 개의 물건을 작은 배낭(최대 무게 < k)에 담는게 작은 문제에 해당한다. 

 

해당 식은 다음과 같고, ( 현재 물건의 가치+ 현재물건의 무게를 뺀 만큼의 무게에서 최대 가치 )과 (그 전 행의 값)을 비교해 큰 값을 선택하는 식이다.

$knapsnack[i][j] = max(value+knapsnack[i-1][j-weight], knapsnack[i-1][j])$

 

위 식을 반복하면서 아래의 행렬을 채우는 문제가 된다.

물건의 개수가 4개이고 최대무게가 7일 때의 문제에서 다음과 같은 배열을 채우는 문제가 되겠다.

 

여기서 핵심 컨셉은, 그 전 row의 값은 최적의 값이라는 것이다.

담는 물건의 개수와 최대 무게를 늘려가면서 순차적으로 얻은 최적의 값이라는 것이다.

즉 2행 7열에서 비교한 (6+8), (13)에서 ,
8은 2개의 물건을 사용해서 최대 무게 4에서 얻을 수 있는 최대 가치를 의미하고
13은 2개의 물건을 사용해서 최대무게 7에서 얻을 수 있는 최대가치를 의미한다.

 

구현한 코드는 아래와 같다.

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6) # 파이썬 최대 재귀깊이 높이기

stdin = open('12865/sample_input.txt', 'rt') # 테스트할 때, 제출할 때는 주석처리 해주기

n, k = map(int, stdin.readline().split())

things = []
for _ in range(n):
  w, v = map(int, stdin.readline().split())
  things.append((w, v))

# 계산하기 편하게 0~k까지 만들어서, index 1~k까지로 구현하기
value_list = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1, n+1):
  for j in range(1, k+1):
    # 현재 물건의 가치와 무게
    value = things[i-1][1]; weight = things[i-1][0]
    
    # 아직 담을 수 없다면, 그 전 row에 있는 값 그대로 
    if (j < weight):
      value_list[i][j] = value_list[i-1][j]
    # value_list[i-1] 행은 그 전까지 구해놓은 최적의 값들을 의미
    else: 
      value_list[i][j] = max(value + value_list[i-1][j-weight], value_list[i-1][j])

print(value_list[n][k])

 

---

DP를 푸는 방법 중 배열을 채워나가는 방법도 있다는 사실을 기억하고 다음에 사용하자.