[백준12865&파이썬] 0-1 냅색문제(배낭문제)

# 문제

백준 12865 평범한 배낭 파이썬 풀이

12865번: 평범한 배낭

# 코드

import sys

def print2D(arr) :
  for i in arr :
    print(i)
  return

N,K = map(int,sys.stdin.readline().split())
arr = list()

for _ in range(N) :
  weight, value = map(int,sys.stdin.readline().split())
  arr.append((weight,value))

dp = [[0] * (K+1) for _ in range(N+1)]

# 주요 풀이 방법은, 물건들의 범위를 하나씩 늘려간다
  # 이때 해당 물건까지 사용 할 수 있다는 조건이 생기게 된다.

for i in range(1,N+1) :
  arridx = i-1
  weight, value = arr[arridx]
  for j in range(K+1) :
    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] # 복사해가기

# print2D(dp)
print(dp[N][K])

# 풀이

• 배낭문제는 물건을 쪼갤 수 있는 상황과 쪼갤 수 없는 상황으로 나눈다
• 물건을 쪼갤 수 있는 경우, 무게의 weight당 value(가치)를 계산해서 그리디한 방법으로 풀면 된다.ㅇ
• 해당 문제는 쪼갤 수 없는 경우이기 때문에 조금 어려웠다.

• 행과 열을 한 단계씩 늘려가면서 생각 할 수 있어야 했다.
• 행이 늘어나는 것은 선택할 수 있는 물건의 가지수가 하나씩 추가 된다고 생각하면 된다. 1행은 (6,13)의 물건만 사용하지만, 2행은 [ (6,13) , (4,8) ] 의 물건까지 선택할 수 있는 것이다. 3행이라면 [ (6,13), (4,8), (3,6) ] 의 물건을 사용해서 만들 수 있는 최대의 가치를 구한다는 뜻이다.
• 각 열을 순회하면서는, 가방의 최대 가치를 조금씩 늘려가는 것이다. 즉, 아래의 for문에서 j는 배낭의 최대가치를 하나씩 늘려가는 것이다.

  for j in range(K+1) :
    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] # 복사해가기

• 결론적으로 배낭의 가치가 하나씩 늘어나고, 물건들을 담고 안담고의 경우가 DP로 하여금 구해진다.
• 추가로 weight <= j를 생각해내는 것이 힘들었다. 이걸 생각하기 위해서는 j가 순회하는 반복문은 배낭의 현재 허용된 최대크기라고 생각 할 수 있어야한다.