백준_12865_평범한 배낭(DP)

n, k = list(map(int, input().split()))
bag = []
for _ in range(n):
    bag.append([int(v) for v in input().split()])

dp = [[0]* (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        if j >= bag[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[i-1][0]]+ bag[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][k])

냅색 알고리즘을 통해 해결할 수 있는 문제

dp는 2차원 리스트를 쓴다. dp의 row는 가방의 들어갈 각각의 물건이고 column은 가방에 들어갈 수 있는 무게에 대해 0부터 최대 무게까지이다.
dp에서 저장해 나갈 정보는 해당 무게에서 물건들에 대한 가치의 최대 값이다.

가치의 정보를 저장해 나갈 때 해당 물건을 넣을 수 있는 경우에는
dp[i][j] = max(dp[i-1][j], dp[i-1]j-bag[i-1][0]]+bag[i-1][1]) 이 식을 통해 dp를 저장해 나가는데
이 부분에서 계산하고 있는 무게에서 현재 물건의 무게를 뺀 부분의 dp 정보와 현재 무게의 가치를 더한 값과 이전 dp의 값을 비교한다.

즉 현재 물건을 넣었을 때가 이득인지 그렇지 않은 경우가 이득인지를 보는것이다.

이런 식으로 저장해 나가면서 최종적으로 최대 무게에서의 최대 가치를 구할 수 있다.