냅색 알고리즘

백준 12865번

import sys
# 냅색 알고리즘
# 파이썬

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

table = [0] * (k+1)
for _ in range(n):
    w, v = map(int, input().split())
    if w > k:
        continue
    for j in range(k, 0, -1):
        if j + w <= k and table[j] != 0:
            table[j+w] = max(table[j+w], table[j] + v)
    table[w] = max(table[w], v)
print(max(table))

간단히 생각하면 n개의 물품을 넣는 경우와 빼는 경우를 n개 만큼 고려해야 한다. 2^n 번의 계산이 필요한데 이렇게 풀면 시간 초과가 날 것이 분명함. 그럼 쓸데없는 계산을 안 해야 한다는 것인데 그렇다면!
1. k 초과일 때 연산을 해줄 필요가 없음
2. 이미 한 계산을 또 하면 안 됨.

따라서, 내가 푼 방식은!

table = [0] * (k+1)

첫번째로 0~k 까지 값을 저장해놓을 수 있는 테이블을 생성할거야.
그리고 이 테이블에 특정 무게에서 얻을 수 있는 최대 v를 기록을 해 놓는 거지. 그래서 새로운 물품이 들어오면 그 물품이 들어갈 수 있는 부분에 새로운 물품의 v를 더해준 후 전체 무게에 해당하는 테이블을 갱신해주는거야.

예를 들어 w=3, v=2 인 물품이 들어왔고 k=7일 때, 무게가 4일 때 현재 테이블에 저장되어 있는 값이 10이면, 7에 해당하는 테이블에 10+2를 넣어주는거지. 그런데 사실 그냥 12를 넣어주면 안 되고 기존에 있는 값과 12중에서 큰 값을 넣어주면 되는거야.