12865번 평범한 배낭 G5

N개의 물건이 있고 각 물건은 무게 W와 가치 V를 갖는다.
가방의 최대 용량은 K이고 가장 가치있게 물건을 담을 때의 값을 구해야 한다.

우선 dp 문제다.
물건 수 N이 100이하기 때문에 다 해볼 수는 없다.

사실 아이디어를 떠올리지 못해서 찾아봤다.
dp 테이블을 N * (K+1) 로 만들어서 사용해야 한다.

dp[N][K]는 가방의 무게가 K일 때 N번째 물건을 넣는 경우, 넣지 않는 경우 중에서 최대 값으로 한다.
즉, dp[N-1][K-W] + V 와 dp[N-1][K] 중 최대 값이 된다. (W와 V는 현재 물건의 무게와 가치)

4 6
2 4
3 5
6 9
1 1

위와 같은 예시가 주어졌을 때 dp 테이블은 아래처럼 된다.

  0 1 2 3 4 5 6
2 0 0 4 4 4 4 4
3 0 0 4 5 5 9 9
6 0 0 4 5 5 9 9
1 0 1 4 5 6 9 10

파이썬 코드

from sys import stdin

n, k = map(int, stdin.readline().split())
items = [list(map(int, stdin.readline().split())) for i in range(n)]

dp = [[0 for i in range(k+1)] for j in range(n)]

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

print(dp[-1][-1])