백준 12865: 배낭문제 (knapsack)(골드 V) - DP

배낭 문제 (0-1)

(독백체 글)
오랜만에 알고리즘 연습을 하려고 한다. 배낭 문제는 DP를 입문할때 반드시 거치는 문제인데 제대로 연습해보고자 다시 한 번 풀었다.

DP가 어려운 이유는 점화식을 세우는 것이 대단히 어렵다고 느낀다. 배낭문제를 처음 접하면 이 역시 점화식을 세우기 쉽지 않고 어떻게 접근해야하는지도 막막하다.

https://www.acmicpc.net/problem/12865

간단히 말하면 100개 이내의 물건은 각각 무게와 가치를 가지고 있고. 이를 K kg이내로 물건들을 최대로 담을 수 있을 때, 물건을 어떻게 담아야 최고의 가치를 얻을 수 있는지를 묻는다. 문제 이해 자체는 어렵지 않다.

당연히 모든 경우의 수를 탐색하는 완전 탐색을 생각해 낼 수 있지만 물건들을 담냐 or 안담냐로 물건마다 2개의 경우의 수가 생긴다.

예를 들어 물건이 4개가 있으면 2 * 2 * 2 * 2 = 16가지의 경우의 수가 생기며 이는 O(2^n)을 가진다. 컴퓨터가 일반적으로 1초당 1억번의 연산을 진행한다고 하면 최대로 시간내에 완전탐색으로 연산을 할 수 있는 물건 개수는 26개 $ 2^26= 67,108,864 $이다. 

하지만 물건의 최대 개수는 100개이기 때문에 경우의수가 100양 (억,조,경,해,자,양....ㅎ) 을 넘어 시간 제한 2초내에 절대 못푼다. (쓸데없는 연산을 진행했지만 그냥 궁금해서,,)

---

결국엔 DP를 사용해야하는 문제인데, 이를 아주 쉽고 차근차근 이해하려고 글을 썼다. 왜 dp를 사용하는지, 어떻게 점화식을 만들어가는지에 대해 정리한다.

1) 문제 관찰

- 가치합의 최대값을 구하라는건 결국 최적화 문제이다. 현재 상황에서 최적의 상황을 고를 수 없기 때문에 그리디 알고리즘은 사용할 수 없다. 그렇다면 DP를 떠올릴 수 있다. DP의 조건을 떠올려보면 작은 문제로 나뉘어질 수 있다. 그리고 메모라이제이션이 가능하다.

먼저 각 물건을 넣을지 말지 결정해야한다. DP는 이런 선택 문제를 단계적으로 해결하는데 강점이 있다. 또한 K라는 제한 조건이 있기 때문에 가능한 경우의 수를 나눠가며 해결한다.

문제를 읽으면서 "최댓값", "최적화"와 같은 단어들이 나오면 DP를 고려해볼 수 있다. 이 문제에서는 가치의 합의 최댓값을 구하는 것이다.

그리고 배낭 문제에는 0-1배낭문제와 무한 배낭 문제가 있는데, 이 문제는 물건을 넣을지 말지 결정하는 것으로 이는 0-1배낭 문제이다.

2) 문제 쪼개기

- 작은 문제로 나뉘어질 수 있는지 확인해야한다. 문제를 가장 작게 쪼개면 다음과 같아진다.

현재 무게 한도(K)에서, 1번째 물건만 고려했을 때의 가치는?
--> 1~2 번째 물건을 고려했을 때의 최대 가치는?
--> ...
--> 1~N 번째 물건까지 고려했을 때, 무게 K를 넘지 않는 최대 가치는?

이와 같이 작은 문제를 해결하면서 점차 큰 문제로 확장해 나가는 방식이 DP의 핵심이다.

3) DP 적용 가능성 확인

1. 최적 부분 구조 (Optimal Substructure)
- 큰 문제의 답을 작은 문제의 답으로 구성 가능한가?
: "N번째 물건까지 고려한 최댓값"은 "N-1번째 물건 까지의 최댓값"을 이용해서 구할 수 있다.

2. 중복되는 부분 문제
- 동일한 부분 문제를 여러 번 계산이 필요한가?
: 그렇다. N번째 물건을 고려할 때 N-1번째 고려된 물건의 경우를 다시 연산해야한다.
--> 메모이제이션이 가능하다.

---

이제 DP를 써도 괜찮다는 결론이 나왔으므로 점화식을 도출해야한다.

1) 점화식 정의

"현재 상태를 이전 상태로부터 어떻게 계산할 것인가?" 이 질문이 핵심이 된다.

DP테이블 부터 정의하면 dp[i][k], i는 물건의 인덱스, k는 현재 배낭의 남은 무게를 의미하며
[i번째 물건까지 고려했을 때, 배낭의 남은 무게가 k일 때 얻을 수 있는 최대 가치]의 의미를 가진다.

즉 dp[0][k]는 물건이 하나도 없을 때, 배낭의 남은 무게가 k일 때의 최대 가치는 0이라는 초기 조건을 가진다.

i번 째 물건을 넣을지 말지 결정해야하고 이에 따라 두 가지의 경우로 나뉘어진다.

• i번째 물건을 넣지 않는 경우:
  
  • 이 경우 dp[i][k] = dp[i-1][k]
    즉, i번째 물건을 고려하지 않고 이전 상태를 그대로 유지한다.
• i번째 물건을 넣는 경우:
  • i번째 물건의 무게가 k를 초과하지 않는다는 조건에서
  • i번째의 물건의 무게와 가치를 반영하여 계산한다. 즉,
  • dp[i][k] = dp[i-1][k-W[i]] + V[i] (W: 무게, V: 가치)
  • 구체적으로 살펴보면
    • 1. 이전 상태: dp[i-1][k-W[i]]
      • i-1번째 물건까지 고려했을 때, 배낭의 남은 무게가 k-W[i]인 상황에서의 최대 가치이다.
      • 즉, i번째 물건을 배낭에 넣기 위해, 배낭의 남은 무게 k에서 i번째 물건의 W[i]를 뺀 상태를 고려한다.
      • 왜냐면 이 상태에서 물건을 다시 넣을 거니까.
    • 2. i번째 물건의 가치 추가
      • + V[i]
      • i번째 물건을 배낭에 넣었으므로, 그 물건의 가치를 추가한다.
    • 3. 결과적으로
      
      • i번째 물건을 넣었을 때, 배낭의 무게 한도가 k일 때 얻을 수 있는 최대 가치는 "이전 상태에서 W[i]만큼의 무게를 소모하고, i번째 물건의 가치를 더한 값" 이다.

2) 다시. 직관적으로 

i번째 물건을 넣는다.
- i번째 물건을 넣으면 배낭의 남은 무게가 줄어들고(-W[i]) 대신 i번째 물건의 가치가 추가된다. (+ V[i])
- dp[i][k] = dp[i-1][k-W[i]] + V[i]

i번째 물건을 넣지 않는다.
- i번째 물건을 넣지 않으면 i-1번째 상태 그대로 유지한다.
- dp[i][k] = dp[i-1][k]

그렇다면?

최적의 경우는 이 두 가지 경우에 대해 더 큰 값을 가지는 것으로 매핑하면 된다.

최종 점화식: dp[i][k]=max(dp[i−1][k], dp[i−1][k−W[i]]+V[i])

---

코드구현

N, K = map(int, input().split())
items = []  # (무게, 가치)
for _ in range(N):
    W, V = map(int, input().split())
    items.append((W, V))

dp = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    W, V = items[i - 1]
    for k in range(K + 1):
        
        dp[i][k] = dp[i - 1][k]
       
        if k >= W:
            dp[i][k] = max(dp[i][k], dp[i - 1][k - W] + V)

print(dp[N][K])

 

DP를 1차원으로 사용할 경우

N, K = map(int, input().split())
items = []
for _ in range(N):
    W, V = map(int, input().split())
    items.append((W, V))

dp = [0] * (K + 1)

for W, V in items:
    for k in range(K, W - 1, -1):  # 역순으로 순회
        dp[k] = max(dp[k], dp[k - W] + V)

print(dp[K])

시간복잡도
2차원 DP: 𝑂(𝑁×𝐾)
1차원 DP: 𝑂(𝑁×𝐾)
공간복잡도
2차원 DP: 𝑂(𝑁×𝐾)
1차원 DP: 𝑂(𝐾)