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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

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

 

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

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

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

이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 만드는 프로그램을 작성하시오.

단, 각 종류별 보석의 개수는 무한정 존재하며 한 종류의 보석을 여러 번 가방에 담을 수 있다.

 

 

*입력 설명

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

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

단, 가방의 저장무게는 1000kg을 넘지 않는다. 

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_80.txt', 'rt')

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])
    
# 출력 : 28

 

input_80.txt(입력)

4 11
5 12
3 8
6 14
4 8

 

 

중요내용

1. 특정 무게까지 보석을 담았을 때, 해당 보석들의 최대가치를 리스트 dy에 저장한다.
2. 즉, dy[j]는 총 무게가 j인 보석들의 최대가치를 의미한다.
3. for j in range(w, m+1): 는 w무게를 가방에 추가할 때, w이하의 무게는 고려할 필요가 없기 때문에 range의 범위가 1부터 시작하지 않고 w부터 시작하는 것이다.
4. dy[j] = max(dy[j], dy[j-w]+v)는 가방에 j무게까지의 보석을 담을 때, 기존의 보석 가치와 w무게의 보석을 추가(j-w)할 경우 얻는 새로운 보석 가치를 비교하여 더 큰 값을 dy[j]에 저장하는 코드이다.