[알고리즘][Python] 백준 12865 평범한 배낭 문제 풀이

문제 출처 : www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

문제 해석 : 배낭에 최대한의 가치를 가지도록 물건을 채워넣어서 여행을 갈려고 한다. 이때 배낭의 최대무게까지 들고 갈 수 있는 물건의 최대 가치를 구하라

 

문제 풀이 :  배낭 정리 알고리즘을 이용해서 풀이할 수 있다.

---

풀이 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.insert(0, [0,0])

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

for i in range(1, N + 1):
    for j in range(1, K + 1):
        Weight, Value = arr[i]

        if j < Weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(Value + dp[i-1][j-Weight], dp[i-1][j])

answer = dp[N][K]

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.