[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 8

가방문제(냅색 알고리즘)

최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

▣ 입력설명
첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.
두 번째 줄부터 각 보석의 무게와 가치가 주어진다.
가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

▣ 출력설명
첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

▣ 입력예제 1
4 11
5 12
3 8
6 14
4 8

▣ 출력예제 1
28

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

data = []
n, limit = map(int, input().split()) #보석 종류, 무게 한계값
dp = [0] * (limit + 1)

for i in range(n):
    w,v = map(int, input().split()) #무게, 가치
    for j in range(w , limit + 1): #현재 적용하고자 하는 무게부터 돌아야지
        #이렇게 안할거면 if문으로 따로 조건 걸어야해!
        dp[j] = max(dp[j], dp[j-w] + v)  #현재 보석을 가방에 담을 것이라고 가정한 값이 dp[j-w] + v 이다.

print(dp[limit])

코멘트

이해가 안가는 냅색 알고리즘... 다시 공부해야한다.