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

생성일: 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] 값을 갱신한다.