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

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

내가 푼 풀이

풀이 방법

1. 최대 무게의 길이만큼다이나믹 테이블을 하나 만든다.
2. 다이나믹 테이블에서 무게를 더한 것을 인덱스로 해서 테이블에서 가장 큰 가치를 가지는 값으로 바뀌게 한다.

import sys

n, m = map(int, input().split())
gems = []
max_val = 0
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    gems.append([a, b])

dy = [-1] * (m + 1)
dy[0] = 0
for i in range(m + 1):
    if dy[i] != -1:
        for gem in gems:
            if gem[0] + i <= m:
                if dy[i + gem[0]] < dy[i] + gem[1]:
                    dy[i + gem[0]] = dy[i] + gem[1]
print(max(dy))

코드를 일단 작성해보았는데 동작은 잘된다.
하지만 다른 코드를 보았을 때 보다 직관적이지 않고 매우 산만한 코드인 것 같다.

다른 코드

import sys
sys.stdin = open("input.txt", 'r')    
if __name__=="__main__":
    n, m=map(int, input().split())
    dy=[0]*(m+1);
    for i in range(n):
        w, v=map(int, input().split())
        for j in range(w, m+1):
            dy[j]=max(dy[j], dy[j-w]+v)
    print(dy[m])

이 코드는 보석 하나의 무게와 가치를 받을 때마다 다이나믹 테이블을 갱신시켜주었다.
그리고 나서 최대값을 비교하는 것도 max함수를 통해 한줄로 직관적으로 구현했다.