가방문제 (냅색 알고리즘)
생성일: 2022년 2월 25일 오후 4:04
구현 코드 ⭐
# 가방 문제 (냅색 알고리즘)
import sys
sys.stdin = open("input.txt", "rt")
if __name__ == "__main__":
N, W = map(int, input().split())
dy = [0]*(W+1) # dy[j] 는 가방에 j무게만큼을 담을 수 있을 때 최대 가치
for i in range(N):
w, v = map(int, input().split())
for j in range(w, W+1):
dy[j] = max(dy[j], dy[j-w]+v)
print(dy[W])
- 이 문제는 같은 종류의 보석을 여러번 넣을 수 있다는 가정 하에 짜여진 코드이다.
- 로직
- 보석의 정보를 하나씩 가져오게 되는데, 중요한 아이디어는 해당 보석을 가방에 넣는다고 가정하는 것이다.
- dy리스트에서 dy[j] 는 가방에 j무게만큼을 담을 수 있을 때 최대 가치를 의미한다.
- 따라서, 특정 보석 정보를 받아오고 해당 보석을 가방안에 넣는다고 가정하면 dy[j-w]는 해당 보석이 가방안에 들어가고 가방의 남은 용량에서의 최대가치이다. dy[j-w]+v 는 해당 보석을 넣고 난 후에 가방에 들어있는 보석들의 총 가치이다.
- 기존에 j만큼 용량의 가방에서 최대가치를 계산해놓은 값인 dy[j]와 새로운 보석을 넣었을 때 j만큼 용량의 가방에서의 최대가치인 dy[j-w]+v를 비교하여 더 가치가 높은 것을 채택하여 dy[j] 값을 갱신한다.
Author And Source
이 문제에 관하여(가방문제 (냅색 알고리즘)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/가방문제-냅색-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)