728x90
> Dynamic programming(동적계획법)
📖 문제 : 가방문제(냅색 알고리즘)
최고 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
해설 : 5g 1개, 3g 2개를 선택해서 28가치가 최대이다.
코드
if __name__ == "__main__":
n, m = map(int, input().split())
bag = [0]*(m+1)
for i in range(n):
w, v = map(int, input().split())
for j in range(w,m+1):
bag[j] = max(bag[j],bag[j-w]+v)
# temp = bag[j-w]+v
# if temp > bag[j]:
# bag[j]=bag[j-w]+v
print(bag[m])
Point ! ⭐️
- bag 리스트를 정의하면 bag[5]는 무게 5가 최대인 가방에 들어갈 수 있는 보석의 최대 가치이다.
주어진 보석 갯수대로 for문을 돌리면서
예를 들어, 아래의 예시를 보면
4 11 (4는 보석의 종류 갯수, 11은 가방에 들어갈 수 있는 최대 무게)
5 12
3 8
6 14
4 8
1) (무게w, 가치v) = (5, 12) 인 첫번째 보석을 먼저 보면
이중 for문으로 5~11 까지 돌리면서
bag[j] = bag[j-w]+v의 식을 적용시켜주는 것이다. 그러면
bag[5] = bag[0]+12 = 12
...
bag[10] = bag[5] + 12 = 24
이런식으로 보석 하나당 무게를 늘려가면서 들어갈 수 있는 최대 무게를 각각 넣어주는데
2) (무게w, 가치v) = (3, 8) 인 두번째 보석일 때에는
이미 1)으로 bag = [0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 24, 24] 인 상태에서
bag[3] = bag[0] + 8 = 8
bag[5] = bag[2] + 8 = 8인데 위에서 bag[5]는 12이라는 값이 이미 들어가 있기에 12값을 그대로 놔둔다.
...
bag[6] = bag[3] + 8 = 16이므로 기존 값 12 보다 크므로 16값으로 바꿔주면 된다.
bag[8] = bag[5] + 8 = 12 + 8 = 20 이 기존값 12보다 크므로 20을 바꿔준다.
=> 여기서 20은 (무게 5 보석 1개 (가치 12) + 무게 3인 보석 1개 (가치 8))
이렇게 한바퀴 다 돌면 bag 리스트는 아래의 모습처럼 바뀐다.
bag = [0, 0, 0, 8, 8, 12, 16, 16, 20, 24, 24, 28]
... 보석의 갯수대로 계속 반복하는 것 ! 이게 바로 냅색 알고리즘 ~!!!!
출처
- 인프런 : 파이썬 알고리즘 문제 풀이
728x90