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

<문제>

최고 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

<설명>

일단 DP 테이블을 0으로 초기화 한 길이가 가방의 최대 무게 길이만큼 만든 후에 DP[j] 값과 DP[j-w] + v 값 2개 중에서 가장 큰 값을 DP[j] 값에 넣는다. 반복문은 무게 인 값부터 시작을 한다.

이게 무슨 말이냐면 첫번째 보석의 무게는 5 가치는 12인 보석부터 시작을해서 이 보석을 가방에 무조건 넣는다고 생각을 하면서 계산을 하는것이다. 이 보석을 가방에 집어넣을수 있으면 DP[j] 값과 DP[j-w] + v 중에 가장 큰 값을 넣어야 한다. j-w인 이유는 예를들어 j가 10일때 해당 D[j-w] + v 의 의미는 해당 보석을 가방에 넣을 때 를 생각하면 j-w 무게를 생각했을때 해당 가방의 최대 가치에 해당 보석을 넣는 값이 된다.

이런식으로 DP테이블을 계산한 후에 DP[11] 의 값을 출력하면 된다.

 

<코드>

n , m = map(int,input().split())
DP = [0] * (m + 1)
for i in range(n):
    w, v = map(int,input().split())
    for j in range(w,m+1):
        DP[j] = max(DP[j],DP[j-w] + v)
print(DP[m])