문제 / 배낭(가방) 문제 - 냅색알고리즘 Knapsack algorithm / Python 파이썬

 

문제 제목: 가방 문제

가방문제(냅색 알고리즘) 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.

이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다.

 

---

냅색알고리즘 

 

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

예를 들어 보석 종류의 개수는 4개, 무게의 한계 값은 11이라고 하자

 

1. 가방에 담을 수 있는 최대 보석의 무게의 한계값 만큼 리스트를 만든다.

 

 

for 문으로 해당 dy 리스트를 순회할 것이다.

dy[j] : 가방에 j 무게 보석의 최대 가치

 

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

첫번째 입력 : 5, 12

 

dy[j-w] + v

 

대충 의사코드를 짜보면

for j in range(len(dy)):
	if j >= w: # j가 w(보석 무게)보다 커야 리스트에 저장 가능
    		dy[j] = v + dy[j-w]

 

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])

순회를 하면서 해당 값이 더 큰지 확인을 하고, 더 큰값을 저장해나감

최종적으로 m번째 값을 출력한다.

 

---

※ 알아야 할 것

- 변형된 것은 플로이드워샬 알고리즘