[Knapsack DP] 냅색은 바텀업으로 - 연습문제 유형익히기

지난 포스팅에 knapsack은 탑다운보단 바텀업을 짜는 것이 훨씬 유리하다고 작성한 적이 있다.

(아래 포스팅 참고)

https://kth990303.tistory.com/207

[Knapsack] 냅색은 웬만해선 바텀업으로 짜자

이번 포스팅에선 knapsack 문제 유형을 익혀보고 공부해보는 시간을 가져볼 것이다.

 

knapsack에서 개인적으로 중요하다 생각하는 것은 아래와 같다.

• 이 문제가 knapsack dp 풀이를 요구하는지
• for문 순서를 어떻게 짜야 하는지 (어떤 것이 먼저 갱신돼야 하는지)
• 중복 허용 여부

사실 제일 중요한 것은,

이 문제가 knapsack dp로 해결이 되는지를 파악하는 것이라 본다.

dp인지 그리디인지, 아니면 bfs인지 수학인지 누적합인지... 알고리즘 분류를 보지 말고 푸는 연습을 하는 것은 그만큼 중요하다. 

그러나, 이번 시간은 애초에 knapsack dp를 바텀업으로 연습하는 시간이기도 하니까, 그만큼 "knapsack DP를 써주세요!" 라고 외치는 문제들을 살펴볼 것이다.

---

가장 Well-Known인 Knapsack DP

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

12865번: 평범한 배낭

각 물건들을 중복을 허용하지 않고 개수에 상관없이 무게 K 이하로 최대의 가치를 내야 하는 문제이다.

위와 같이 두 개의 조건을 고려하여 넣었다가(1) 뺐다가(0)의 여부를 결정하는 것을 0-1 knapsack dp라고 한다.

배낭 문제는 굉장히 유명해서 알고리즘을 공부해본 사람들이라면 누구나 알 것이라 생각해 웰노운으로 소개하였다.

 

dp[i]: 무게 i일 때 가능한 최대의 가치합이라고 정의해보자.

 

이 때, 무게 i는 어떠한 물건 w[j]를 담기 이전 무게 i-w[j]에서 w[j]만큼 더해지면 가능하므로, 

d[i]=d[i-w[j]] + v[j] (가치: v[j]) 로 나타낼 수 있다.

---

1. 만약 for문을 아래와 같이 세웠다고 생각해보자.

for(int i=0;i<n;i++){
	for(int j=0;j<=K;j++){
    		if(j-w[i]<0) continue;
    		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    	}
}

 j-w[i]<0 일 경우, d[j-w[i]] 부분에서 OutOfIndex 런타임 에러를 띄울 것이기 때문에 continue; 처리를 해주었다.

 

물건 순회(i)보다, 특정 물건을 담을 때의 무게/가치 변화 여부(j)가 먼저 갱신된다.

바텀업으로 dp를 접근할 때엔, 어떤 것이 먼저 갱신돼야 하는지 고민해봐야 for문 순서를 명확하게 짤 수 있다.

 

위와 같이 짤 경우, dp[i+w[j]]=max(dp[i+w[j]], dp[i]+v[j]) 와 같이 처음부터 올라가기 때문에, 물건이 중복해서 담길 수 있다. 

 

2. 만약 for문을 아래와 같이 짰다고 생각해보자.

for(int i=k;i>=1;i--){
	for(int j=0;j<n;j++){
		if(i-w[j]<0)continue;
		dp[i]=max(dp[i],dp[i-w[j]]+v[j]);
	}
}

 

이번엔 무게 갱신(i)를 물건 탐색(j)보다 먼저 갱신해주었다.

그리고 무게 갱신은 큰 것부터 진행해주었다.

얼핏 보면 순서 상관없이 될 거 같아 보인다. 그러나, 잘 생각해보면 (또는 디버깅해보면) dp[k]를 구하려는 것인데, dp[0]~dp[k-1]까지의 값들이 전혀 갱신이 되지 않아 두 개 이상의 물품을 담는 무게가 나오지 않음을 확인할 수 있다.

 

3. 만약 for문을 아래와 같이 짰다고 생각해보자.

for(int i=0;i<=k;i++){
  for(int j=0;j<n;j++){
    if(i-w[j]<0)continue;
    d[i]=max(d[i],d[i-w[j]]+v[j]);
  }
}

가장 그럴듯하게 보이는 오답 순서이다.

dp[0]~dp[k-1]까지 갱신이 됐으므로 dp[k]도 답이 잘 나올 것처럼 보인다.

그러나, 아까 1번 for문에서 언급했듯이, dp[0]~dp[k-1]까지 순서대로 갱신해버릴 경우, 중복을 허용해버린다.

따라서 아래 예제입력이 아래 결과가 나온다.

5 7
6 13
4 8
3 6
5 12
2 7
output: 21 (무게가 2이면서 가치가7인 물건*3)
// 정답은 19다.

 

4. 만약 for문을 아래와 같이 짰다고 생각해보자.

for(int i=0;i<n;i++){
  for(int j=k;j>=0;j--){
  	if(j-w[i]<0) break;
  	d[j]=max(d[j],d[j-w[i]]+v[i]);
  }
}

j를 가장 큰 무게부터 세주기 때문에 중복 허용하지 않고 카운트할 수 있다.

그런데, dp 갱신은 dp[0]~dp[k-1]까지 갱신하지 않고 해줘도 올바른 결과값이 나올 수 있나?

그렇다. 위 for문 순서는 무게 갱신을 먼저 해주고, 물건 탐색을 나중에 갱신해주기 때문에, 1번 물건을 담을 때 무게 갱신, 2번 물건을 담을 때 무게 갱신, ... 을 해주기 때문에 dp[0]~dp[k-1]이 갱신된 후에 다음 물건을 탐색해주기 때문에 올바른 답이 나온다.

 

정답 코드(C++17, 12ms): https://www.acmicpc.net/source/share/67a02fdbee0e4250997d86eec81400b8

---

for문 순서에 따라, 그리고 중복 허용 여부에 따라 knapsack 바텀업 식이 얼마나 달라지는지,

이번 기회에 직접 디버깅하면서 몸소 느꼈으면 좋겠다.

 

그럼 연습문제들을 투척하고 포스팅을 마치겠다.

 

1. Coins (Gold V) https://www.acmicpc.net/problem/3067

위에서 풀었던 문제와 거의 비슷하나, 중복을 허용해준다.

위 포스팅을 꼼꼼히 읽었다면 어떻게 풀어야할지 바로 감이 올 것이라 생각한다.

참고로 탑다운으로 풀 경우, 웬만한 최적화가 아닌 이상 '시간초과'가 당신을 반갑게 맞이할 것이다.

 

2. Piggy-Bank (Gold V) https://www.acmicpc.net/problem/3483

영어 문제이긴 한데, 결국은 F-E의 무게로 가능하면서 최소한의 돈으로 가능한 값을 뽑으라는 말이다.

위에서 본 문제와 달리, 이번엔 최소값을 구해야 한다.

dp 배열을 처음에 어떻게 세팅하면 좋을까?

 

3. Buying Hay (Gold IV) https://www.acmicpc.net/problem/6066

이 문제도 영어문제인데, 꽤나 재밌어서 들고 왔다. (21.11.23. 에 풀어서 뒤늦게 이 포스팅에 추가했다.)

특정 무게를 구매하기 위해 필요한 최소비용이 아닌, 특정 비용 이상을 구매하기 위해 필요한 최소비용이다.

같은 말처럼 느껴질 수 있는데, 만약 위 문제들과 똑같이 해결한다면 맞왜틀을 할 수 있다.

오히려 더 많은 무게를 살 때가 더 싼 경우가 존재하기 때문이다.

잘 생각해보자.

 

4. 사탕 (Gold II) https://www.acmicpc.net/problem/1415

중복을 허용하는데, 같은 것을 처리하는 게 조금 걸리적거리는 문제이다.

소수는 에라토스테네스 체를 이용해 O(Nlog(logN))에 구해주자.

그리고 조금만 더 생각해보자. 같은 것들은 중복을 허용하는데, 같지 않은 것들은 중복을 정말 허용하고 있을까?

이를 이용해 for문 순서를 잘 구현해보자.

그리고, 예외 처리를 해야될 것 또한 존재하는 문제이다.

---

그렇다고 탑다운 dp를 버리진 않았으면 좋겠다.

탑다운으로 풀면 굉장히 쉬운데, 바텀업으로 풀면 좀 어렵게 느껴지는 문제(이전 행동이, 다음 행동에 그대로 영향을 미치면서 재귀로 표현하기 굉장히 쉬운 문제라든지...)들도 꽤나 있기 때문이다.