백준 12865) 평범한 배낭 (골드.5)

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

12865번: 평범한 배낭

무게가 제한된 가방에 넣을 수 있는 물건들의 최대 가치를 찾는 문제이다. 

 

냅색(Knapsack) 알고리즘으로 유명한 문제다. 

global n, k, product, isUsed
n, k = map(int, input().split())
product = []
dp = [0] * (k+1)
for _ in range(n):
    w, v = map(int, input().split())
    for j in range(k, w-1, -1):
        dp[j] = max(dp[j-w]+v, dp[j])
print(max(dp))

 

 

( 문제풀이에 참고한 사이트)

https://myjamong.tistory.com/319

백준 12865 파이썬 - 평범한 배낭 - 동적 계획법

https://hongcoding.tistory.com/50

[백준] 12865 평범한 배낭(Python 파이썬)