[알고리즘] 백준 12865번 : 평범한 배낭

백준 12865번 : 평범한 배낭(문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 동적 프로그래밍(DP)
• 난이도 : 하

소스코드

import sys

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

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

for i in range(1, n+1):
    weight, value = map(int, sys.stdin.readline().split())
    for j in range(1, k+1):
        if j < weight:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

print(dp[n][k])

설명

• 이 문제는 아래 표에서 0-1 Knapsack Problem에 해당하는 문제이다.
• 전형적인 DP문제이다. (반드시 알아두기!)
• 물품수 n, 무게 제한 k일 때 O(nk)로 해결 가능

0-1 Knapsack Problem	Fracktional Knapsack Problem
물건 쪼갤 수 없음	물건 쪼갤 수 있음
동적 프로그래밍으로 해결 가능	그리디로 해결 가능(무게 당 가치가 큰 것 순으로 담으면 됨)

• 이 글(링크)이 배낭 문제를 이해하는데 아주 큰 도움이 됐다!!!(감사합니다ㅠㅠ)

---

• 우선적으로 이 문제를 해결하기 위한 점화식은 다음과 같다. 이 점화식을 그대로 코드로 옮기면 된다. 점화식이 의미하는 바를 하나씩 살펴보자. (위 링크의 글을 참고하여 작성함)
  

  

  • i : 물품의 개수 , j : 배낭 무게 한도
  • D는 2차원 리스트이다.
  • D[i][j] : i개의 물건이 있고, 배낭의 무게 한도가 j일 때 최적의 가치를 의미한다.
  • W[i], V[i] = i번 째 물건의 무게, 가치
  • 1)번식 : i번 째의 물건의 무게가 배낭의 무게 한도보다 크다면, 배낭에 i번째 물건을 담을 수 없으므로 i번 째 물건을 제외한 i-1개의 물건을 가지고 구한 전단계의 최적의 가치를 그대로 가져온다.
  • 2)번식 : 1)이 아닌 경우, i-1개의 물건을 가지고 구한 전단계의 최적의 가치와 배낭 무게 한도에서 i번 째 물건의 무게 만큼 비웠을 때 최적의 가치에 i번 째 물건의 가치를 더 한 값 중에 더 큰 것을 선택한다.
• 문제 링크의 예시 데이터를 가지고 점화식과 설명을 토대로 표를 만들어 채워보면 아래와 같다.
  • i가 0인 경우는 배낭에 넣을 물건이 없는 경우, w가 0인 경우는 배낭이 존재하지 않는 경우이므로 첫 번째 행과 열은 전부 0으로 채워 넣고 시작한다.
  • D라는 2차원 리스트를 채워나가면서, 필요한 경우 앞에서 계산했던 다른 칸의 값을 이용하여 다음 칸의 값을 계산하기 때문에 이 문제가 DP문제인 것이다.