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

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

---

최고 17kg의 무게를 저장할 수 있는 가방이 있다.

그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다.

이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.

이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요?

각 종류별 보석의 개수는 무한이 많다.

한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

입력설명

첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.

두 번째 줄부터 각 보석의 무게와 가치가 주어진다.

가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

출력설명

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

테스트케이스

입력예제	출력예제
4 11 5 12 3 8 6 14 4 8	28
5 16 5 12 3 8 6 14 4 8 7 18	42
10 30 5 11 3 8 6 14 4 8 7 18 2 6 13 28 9 19 10 20 11 23	90

---

해결방법

냅색 알고리즘

1. 다이나믹 테이블 dt 생성
2. dt 값은 0으로 초기화
3. 테이블 인덱스 의미는 가방의 인덱스 크기 만큼 최대로 담을 수 있는 무게 보석의 최대 가치
   
   

예) dt[2] : 가방에 담은 2kg 최대 그 가치 값
(만약 가방이 2kg 일 경우 가장 최대의 보석 가치 값)

1. dt[j] = dt[j-w] + v (처음 j는 현재 w값이고 계속 증가할 것이다, 가방 최대 값까지 j는 증가)
   만약 이 dt[j-w] + v 로 만들어진 값이 dt[j] 안에 값이 있을 경우 만들어진 값과 비교하여 dt[j-w]+v가 더 크면 dt[j]에 넣는다.

동작 시각화

위의 과정을 계속 반복한다!!!

---

코드

n, kg = map(int, input().split())

rocks = [list(map(int, input().split())) for _ in range(n)]

# dt 안에 값의 의미
# dt[0] : 0kg 가방안에 최대한의 가치로 채울 수 있는 방법
# dt[1] : 1kg 가방안에 최대한의 가치로 채울 수 있는 방법 ...

dt = [0] * (kg + 1)

for rock in rocks:
    for j in range(rock[0], kg + 1):
        # 안에 있는 값보다 큰 것 대입
        # rock[0] : 돌의 무게
        # rock[1] : 돌의 가치
        dt[j] = max(dt[j], dt[j-rock[0]] + rock[1])

print(dt[-1])