[BOJ][Python][골5][12865] 평범한 배낭

문제 링크

문제링크

첫 번째 풀이

최대 wegith로 최대 value를 구하는 전형적인 냅색 문제입니다.

	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]
초기값	0	0	0	0	0	0	0	0
(6,13)	0	0	0	0	0	0	dp[0]+13=13	dp[1]+13=13
(4,8)	0	0	0	0	dp[0] + 8 = 8 max(0,8)=8	dp[1] + 8 = 8 max(0,8)=8	dp[2] + 8 = 8 max(13,8)=13	dp[3] + 8 = 8 max(13,8)=13
(3,6)	0	0	0	dp[0] + 6 = 6 max(8,6)=6	dp[1] + 6 = 0 max(8,6)=8	dp[2] + 6 = 0 max(8,0)=8	dp[3] + 6 = 0 max(13,0)=13	dp[4] + 6 = 14 max(13,14)=14
(5,12)	0	0	0	0	0	dp[0] + 12 = 12 max(8,12)=12	dp[1] + 12 = 12 max(13,12)=13	dp[2] + 12 = 12 max(14,12)=12
dp[i]	0	0	0	6	8	12	13	14

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import Counter, deque
from copy import deepcopy

# sys.stdin = open("input.txt", "r")

# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
# n = int(input())
# arr = list(map(int, sys.stdin.readline().split()))

n, k = map(int, sys.stdin.readline().split())
dp = [0] * (k + 10)
arr = [[*map(int, sys.stdin.readline().split())] for _ in range(n)]
# arr.sort(key=itemgetter(1, 0)) 정렬 필요 없습니다. 
for w, v in arr:
    for i in range(k, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(dp[k])

Success Notice: 수고하셨습니다.