[알고리즘 문제 풀이][파이썬] 백준 12865번: 평범한 배낭

백준 12865 문제 링크: https://www.acmicpc.net/problem/12865

📑 문제 설명
1. 필요한 N개의 물건이 있으며 각 물건은 무게 W와 가치 V를 지님
2. 필요한 물건을 배낭에 넣을 시 V만큼 즐길 수 있음
3. 무게의 제한은 K까지 넣을 수 있을 때, 최대로 뽑을 수 있는 V의 값 출력

입력: 첫번 째 줄에 물품의 수와 버틸 수 있는 무게 N, K 주어짐
두번째 줄부터 N개의 줄에 거쳐 각 물건의 무게와 가치 W, V가 주어짐

출력: 최대 가치 V

💡 문제 해결 방법
알고리즘: 냅색 알고리즘 + DP
1. 쪼개지 않는 냅색 알고리즘
2. 가로축은 무게, 세로축은 물건의 개수
3. 이중 반복문을 사용

예외처리 및 추가 내용

💻 코드

import sys

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

bag = [[0 for x in range(k+1)]for x in range(n+1)]

for i in range(1, n+1):
    w, v = item[i - 1]
    for j in range(1, k+1):
        if w <= j:
            bag[i][j] = max(bag[i-1][j], bag[i-1][j-w]+v)
        else:
            bag[i][j] = bag[i-1][j]

print(bag[i][j])

💟 추가적으로 알게 된 점