12865. 평범한 배낭 (with 시온)

같이 푸는 사진

오늘 소마 발표가 끝나고 회의실에서 시간이 남아서 평범한 배낭 문제를 풀었다. 옛날에 답지를 보면서 풀었었는데 오늘 제대로 이해했다. (시온이가 제대로 이해시켜줌)

 

시온이가 말한 접근 방법은 다음과 같다. 우선 dp에는 base case와 점화식이 존재한다. 또한 부분 문제 -> 전체문제로 확장시켜나가는 접근이 좋다고 한다. 

 

배낭문제에서는 단순하게 O(2^n)의 (n은 물건의 개수) 시간 복잡도로 답을 구할 수 있다. 하지만 문제에서 물품의 수는 100개이기 때문에 이렇게 풀면 안된다. 

 

다이나믹 프로그래밍으로 접근하는 방법은 다음과 같다. 물건 하나씩 하나씩 테이블에 기록하며 접근한다. 이 때  점화식은 다음과 같다.

 

dp[here][capacity] = max(dp[here-1][capacity], dp[here-1][capacity-w(here)] + v(here)) 

here은 현재 물건을 말한다.

 

이 때 here - 1이 0보다 작으면 안되므로 base case가 필요하다. 즉 첫번째 물건은 직접 기록해준다.

 

 

 

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

thing = [[0,0]]
d = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    thing.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = thing[i][0]
        v = thing[i][1]

        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

print(d[n][k])