[BOJ12865] 평범한 배낭

[BOJ12865] 평범한 배낭

문제 링크

BOJ12865 - 평범한 배낭

문제 설명

N(1<= N <= 100)개의 물건이 있고, 물건은 각각 무게와 가치를 가진다.

준서가 버틸 수 있는 무게 K( 1<= K <= 십만) 범위 내에서 물건의 가치의 합의 최대값을 구하는 문제이다.

풀이 설명

가장 처음에는 모든 경우의 수를 다 보는 풀이를 떠올렸다.

이 풀이는 각 물건마다

1. 배낭에 넣는다 2. 배낭에 넣지 않는다.

이렇게 두 가지의 경우의 수가 존재하고, N이 최대 100이니까 모든 경우의 수를 다 탐색한다면 이 알고리즘의 O(2¹⁰⁰) 만큼의 시간 복잡도가 된다.

그 다음 떠올린 풀이는 정렬(n log n)을 한 후에 투포인터를 이용한 풀이를 고민해보았다. 하지만, 무게와 가치는 비례한다는 보장이 없기 때문에 무게로 정렬을 하더라도 가치가 정렬되어 있는 상태를 유지하지 않고, 그 반대의 경우도 마찬가지이다. 또한, 각 물건을 배낭에 넣는 경우, 넣지 않는 경우를 모두 확인해야 하기 때문에 이 풀이는 적절한 풀이가 아니라고 판단했다. 이러한 이유로 이진탐색이나 파라메트릭 서치도 적합한 풀이가 아니라고 판단했다.

고민하다보니, 이 문제는 유명한 냅색 문제(Knapsack Problem)라는 것을 떠올리게 되었다. 따라서 2차원 배열의 DP 테이블을 만들어서 Dp[물건 인덱스][배낭의 무게] = 가치의 합 이렇게 데이터를 저장하기로 했다.

먼저 배낭에 넣을 수 있는 경우를 살펴보면 해당 물건을 담아도 배낭의 무게가 K보다 작거나 같은 경우이다.
이러한 경우에는 아래와 같이 표현할 수 있다.

Dp[이전_물건_인덱스][더_넣을_수_있는_배낭의_무게 - 현재_물건의_무게] + 현재 물건의 가치

다음은 배낭에 넣을 수 없는 경우이다. 현재 배낭의 무게와 지금 보고 있는 물건의 무게의 합이 K를 초과하는 경우이다. 이런 경우에는 현재 보고 있는 물건을 배낭에 담지 못하고 건너뛴다. 아래와 같이 표현할 수 있다.

Dp[이전_물건_인덱스][더_넣을_수_있는_배낭의_무게]

더 넣을 수 있는 경우와 넣을 수 없는 경우 중에서 가치의 합의 최대를 계속해서 저장해나간 후, 최종값을 출력하면 된다.

풀이