배낭 문제(knapsack problem)

배낭 문제(knapsack problem)

12865번 - 평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

배낭 문제(knapsack problem)은 담을 수 있는 최대 무게가 정해져 잇는 배낭에 물건들의 가치 합이 가장 크게 되는 경우를 구하는 문제다.

최대 무게를 넘어가는 경우까지 포함해 모든 경우의 수는 물건의 수가 n개일 때, O(2^n)의 시간복잡도를 가진다.

배낭 문제는 대표적인 다이나믹 프로그래밍 문제 중 하나다.

무게가 5 가치가 5인 물건 A, 무게가 3 가치가 3인 물건 B, 무게가 2 가치가 2인 물건 C가 있을 때, 무게가 5 여유있는 상황에서 A를 넣을것인지 B와 C를 넣을 것인지에 대한 연산은 생략이 가능하다. 이렇게 특정 무게에서 최대 가치합이 얼마인지에 대해서 저장해두면 불필요한 연산들을 줄일 수 있다.

dp[k] = '특정 무게에서 가치의 최대 합'
weight = '물건의 무게'
value = '물건의 가치'

for w in range(k, weight-1, -1):
    dp[w] = max(dp[w] + value + dp[w - weight])

각 물건에 대해서 특정 무게에서 가치의 최대 합을 업데이트 해주며 모든 물건에 대해서 이 작업을 수행해주면 자연스럽게 물건이 중복되지 않으면서 특정 무게에서 가치의 최대 합을 구할 수 있다.

중요한 것은 다음 물건들이 사용되지 않은 상태이기 때문에 가능한 경우의 수가 모두 고려될 수 있도록 무게가 0인 상태에서 부터 k인 상태까지 모두 업데이트 해줘야 한다는 것이다.

그리고 높은 무게에서부터 내려오면서 업데이트를 해주어야한다. 0에서 올라가면서 업데이트하면 물건이 중복해서 들어가는 문제가 발생한다.

이렇게 하면 물건의 개수 N과 가방의 최대 무게 K에 대해서 시간 복잡도 O(NK)를 가지게 된다.

추가로 고려해야할 점

여기서 한가지 더 고려해야하는 것이 있다. 위의 문제에서는 '특정 무게에서 최대 가치합'을 기준으로 저장을 했지만 '특정 가치합에서 필요한 최소 무게'를 저장할 수 있다.

이 경우를 고려해야 하는 상황은 K값이 매우커서 O(NK)가 제한된 시간안에 동작하지 못하는 경우다. 이렇게 하면 시간복잡도는 O(N * SUM(cost)) 가 된다.(DP 배열의 길이는 물건들의 비용 총합과 같다)

for cost in range(sum(costs)+1):
    if(dp[cost] <= k): return cost

대신 답을 구하기 위해 추가적으로 배열을 비용이 높은순으로 탐색해 처음으로 필요한 무게가 K이하가 되는 경우를 찾아줘야한다.