[DP] 백준 12865번 “평범한 배낭” Python 풀이

들어가기 앞서,

• 배낭 문제(Knapsack Problem)는 제한된 공간에 가치가 높은 물건들을 최대한 많이 넣는 문제입니다.
• 이 문제는 물건을 나눌 수 있냐 없냐에 따라 두 가지 유형으로 나뉩니다.
  • 분할 가능한 배낭 문제(Fractional Knapsack Problem)
    • 물건을 일부분으로 나눌 수 있는 경우 (예: 설탕 500g 중 300g만 넣기)
    • 그리디 알고리즘으로 해결 가능
  • 0-1 배낭 문제(0-1 Knapsack Problem)
    • 물건을 나눌 수 없고, 전부 넣거나 전혀 넣지 않아야 하는 경우
    • 동적 프로그래밍(Dynamic Programming)으로 해결 가능
• 해당 문제는 0-1 배낭 문제(0-1 Knapsack Problem)에 해당됩니다.

설명

• 문제 설정
  • 물건 개수: N = 4
  • 배낭 용량: K = 7
  • 물건 정보: (무게, 가치) = (6, 13), (4, 8), (3, 6), (5, 12)
• 동적 프로그래밍 테이블 d[n][k] 정의
  • d[n][k]
    • n번째 물건까지 고려했을 때, 배낭 용량 k에서 얻을 수 있는 최대 가치
• 재귀 관계식
  • 현재 물건 i, 현재 물건의 무게 weight, 현재 물건의 가치 value, 담으려는 배낭의 용량 j 일 때
  • 경우 1) 현재 물건을 배낭에 담을 수 없는 경우 (weight > j)
    • d[i][j] = d[i-1][j]
      • 이전 물건을 담았을 때까지의 최대 가치
  • 경우 2) 현재 물건을 배낭에 담을 수 있는 경우 (weight ≤ j)
    • d[i][j] = max( d[i-1][j-weight] + value , d[i-1][j] )
      • d[i-1][j-weight] + value : 현재 물건의 무게만큼 배낭에서 뺀 뒤, 현재 물건을 담았을 때의 최대 가치
      • d[i-1][j] : 현재 물건을 담지 않았을 때의 최대 가치
• 최종 코드
  • 모든 값이 채워진 2차원 DP 테이블의 d[N][K] 값

진행 순서

• 첫 번째 물건(6, 13) 고려

  

• 두 번째 물건(4, 8) 고려

  

• 세 번째 물건(3, 6) 고려

  

• 네 번째 물건(5, 12) 고려

  

예제 코드

import sys

# 물건 개수, 배낭의 최대 용량
n, k = map(int, sys.stdin.readline().split())

# DP 테이블
dp = [[0] * (k+1) for _ in range(n+1)]

# 다루고자하는 물건(무게, 가치) 목록
items = [[0, 0]]
for _ in range(n):
    w, v = map(int, sys.stdin.readline().split())
    items.append([w, v])

for i in range(1, n+1):
    # 현재 물건의 무게와 가치
    w = items[i][0]
    v = items[i][1]

    for j in range(1, k+1):

        # 현재 물건을 배낭에 담을 수 없는 경우
        if (w > j):
            dp[i][j] = dp[i-1][j]

        # 현재 물건을 배낭에 담을 수 있는 경우
        else:
            dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])

print(dp[n][k])

참고

• https://claude-u.tistory.com/208
• https://codingmovie.tistory.com/48
• https://hongcoding.tistory.com/50
• https://velog.io/@keynene/Python파이썬5-백준-알고리즘-12865-평범한배낭
• https://ryu-e.tistory.com/90