[백준] 12865번 - 평범한 배낭 (DP) - 결과 포함

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

이 문제는 해결하지 못하고 다른 분들의 해결 방법을 참고했다.

 

먼저 주어진 물건의 개수와 무게 만큼의 이차원 배열을 생성한다.

 

1번 물건부터 n번 물건까지 하나씩 살펴보는 것이다.

현재 내가 보고 있는 물건이 1에서 k까지 배낭의 무게가 달라질 때마다 가치가 어떻게 달라지는 지를 기록한다.

 

만약에 현재 배낭의 무게가 현재 내가 보고있는 물건의 무게보다 작다면 해당 무게의 이전 물건 가치를 담는다.

그 이유는 현재 내가 보고있는 물건을 담지 못하기 때문에 같은 무게의 배낭에 바로 이전 가치가 최대의 가치이기 때문이다.

 

만약 현재 배낭이 현재 보고 있는 물건을 담을 수 있다면 할 수 있는 행동은 두 가지이다.

물건을 담거나 담지 않거나.

물건을 담지 않는다면 아까와 마찬가지로 해당 배낭 무게의 바로 이전 가치를 담는다.

식으로 나타내면 d[i][j] = d[i - 1][j] 이다.

 

물건을 담는다면 담을 수 있는 배낭의 무게에서 현재 물건의 무게를 뺀 곳의 가치에 현재 물건의 가치를 더해서 저장한다.

현재 물건을 담기까지 기록되어 있는 최대의 가치를 찾은 다음 현재 물건의 가치를 더하는 것이다.

 

물건을 담는 경우와 담지 않는 경우 중에서 더 큰 가치를 갖는 값을 d[i][j]에 저장한다.

 

사실 해결 방법을 참고하고 설명을 읽어도 완벽하게 이해가 되지 않았었다.

아직 다이나믹 프로그래밍 문제를 쉽게 풀지는 못하기 때문에 다른 파트를 연습하고 난 후 다시 계속 풀어봐야겠다.

 

[소스 코드]

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

data = [[0, 0]]
for _ in range(n):
    data.append(list(map(int, input().split())))

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

for i in range(1, n + 1):
    w = data[i][0]
    v = data[i][1]
    for j in range(1, k + 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])