[백준] 12865번 평범한 배낭- 파이썬

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

이 문제는 다이나믹프로그래밍으로 메모지에이션을 활용해서 푼 방법인다.

이문제를 풀기위해 나는 결국에는...? 못풀었지만 다른 분들의 풀이를 참고하며 풀었다

https://claude-u.tistory.com/208

#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘

이분의 풀이를 전적으로 참고했다. 유명한 알고리즘 인가보다.

n, k = map(int, input().split())
stuff = [[0,0]]
bag = [[0]*(k+1) for i in range(n+1)]
for i in range(n):
    w, v = map(int, input().split())
    stuff.append((w,v))

for i in range(1, n+1):
    for j in range(1, k+1):
        weight = stuff[i][0]
        value = stuff[i][1]

        if j < weight:
            bag[i][j] = bag[i - 1][j]
        else:
            bag[i][j] = max(value + bag[i - 1][j - weight], bag[i - 1][j])
        
print(bag[n][k])