[인프런] 가방문제

---

문제설명

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

입력조건

• 첫 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.
• 둘째 줄부터 각 보석의 무게와 가치가 주어진다.
• 가방의 최대 무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

출력조건

• 첫 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

사고과정

• 냅색 알고리즘을 사용해야 한다. 냅색 알고리즘에 대해 잘 몰랐는데 알고보니 예전에 이코테 책에서 풀어본 다이나믹프로그래밍 유형의 문제랑 동일한 것이었다. 
• 중복을 허용하기 때문에 앞에서 부터 차례로 DP 테이블을 Bottom-up 방식으로 갱신해나가면 된다.
• 처음에 못풀었는데 강의에서 아이디어를 보고 구현하는 데는 성공했다. 역시 알고리즘 개념을 알아야 한다..!

풀이(스스로 못 푼 풀이)

n, kg = map(int, input().split())
kind, value = [], []
for _ in range(n):
    k, v = map(int, input().split())
    kind.append(k)
    value.append(v)
dp = [0] * (kg+1)

for i in range(n):
    for j in range(kind[i], kg+1):
        dp[j] = max(dp[j], dp[j - kind[i]] + value[i])
print(dp[kg])