백준 12865) 평범한 가방 - Python

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

12865번: 평범한 배낭

 

1. 문제

 

 

2. 문제 풀이 방식

• 기본적인 0/1 Knapsack 문제이다.
• 우선 무게를 고려해 물건을 담는 경우의 수는 두가지가 있다.
  • 배낭 무게보다 물건이 무거워서 물건을 못담는 경우
  • 물건을 담을 수 있는 경우
    • 여기서 가치를 고려했을 때 두가지 경우가 또 갈라진다.
      • 이 물건을 포함했을때의 가치
      • 이 물건을 포함하지 않았을 때의 가치
      • 이 두 경우를 비교해서는 더 높은 가치를 갖는 경우를 선택해야 한다.

 

• 앞선 경우의 수를 고려해서 점화식을 세워보자.
• 갈수록 가방의 무게가 점점 커지고, 최대로 담을 수 있는 무게인 K 까지 최대한 가치가 높게끔 물건을 담아야 한다.
• 1번부터~ i번째 물건까지를 조합해 j kg의 무게를 담을 수 있는 가방을 채워보자.
  • 무게가 무거워서 현재 탐색중인 i번째 물건을 담을 수 없을때 (불포함)
  • 무게가 가벼워서 현재 탐색중인 i번째 물건을 담을 수 있을 때
    • 여기서 두 경우의 가치를 비교해야 한다.
    • 해당 물건을 담고, 나머지는 이전에 탐색한 물건들로 채우는 경우 (포함)
      • dp[i-1][j-w[i]]+ v[i]
      • 예를 들어 4번 물건을 6kg을 담을수 있는 배낭에 담으려고 할때, 4번 무게를 제외한 나머지 가방의 무게를 1,2,3번으로 채우는 가치의 최대값은 이미 앞서 저장되어있다.
        • dp[3][6kg-5kg]= dp[3][1] : 1번, 2번 물건을 조합하여 배낭의 남은 무게인 1kg을 채우면서 나올수 있는 가치의 최대값
        • 여기서 1, 2,3번 중 어떤 물건의 조합으로 나머지 무게를 채웠는지는 딱히 중요하지 않다. 이미 1,2,3번 물건의 조합을 어떻게든 비교해서 1kg를 채우는 최대가치가 dp[3][1]에 저장되어있기 때문이다.
    • 해당 물건을 담지 않고, 이전에 탐색한 물건들로만 채우는 경우
      • dp[i-1][j]
    • 따라서 두 경우를 비교하면 다음과 같은 식이 나온다.
      • dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])
  • 따라서 마지막 물건인 n번째 물건으로 가방의 최대 무게인 K kg을 채우는 경우의 수까지 모두 탐색하면 해당 무게를 어떤 물건들을 조합해서 채우는게 가장 최대 가치를 갖는지 확인할 수 있다.
• 표를 그려보면서 하면 좀더 명확하게 이해할 수 있다.
  • 1번 물건으로 1kg~7kg을 채우는 최대 가치값
  • 1번으로만 1kg~7kg를 채우는 가치값 vs 2번을 포함해서 1kg~7kg를 채우는 최대 가치값
  • 1, 2번 물건으로 1kg~7kg를 채우는 가치값 vs 3번을 포함해서 1kg~7kg를 채우는 가치값
  • 1, 2,3번 물건으로 1kg~7kg를 채우는 가치값 vs 4번을 포함해서 1kg~7kg를 채우는 가치값

dp[i][j]	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1번 물건	0	0	0	0	0	13	13
2번 물건	0	0	0	8	8	13	13
3번 물건	0	0	6	8	8	13	14
4번 물건	0	0	6	8	12	13	14

 

 

따라서 최종 점화식은 아래와 같다.

 if(j < W[i]):
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])

 

3. Python 코드

import sys

input = sys.stdin.readline
n, k = map(int, input().split())

dp = [[0]*(k+1) for _ in range(n+1)]
W = [0]*(n+1)
V = [0]*n
for i in range(1, n+1):
    W[i], V[i] = map(int, input().split())


for i in range(1, n+1):
    for j in range(1, k+1):
        if(j < W[i]):
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])

print(dp[n][k])

 

 

+) 어렵게 생각하다 보니 자꾸 의문이 생기고 꼬였었는데 혹시 몰라서 정리해두겠음..

 

4. 의문점 - 해결방법

 

1) 왜 그리디가 아니지?

https://hyonee.tistory.com/10

[알고리즘] 그리디 알고리즘 - Greedy Algorithm

 

: 여기를 참고해보면 그때 그때 가장 비싸거나, 무게가 가벼운 걸 선택해도 최적의 알고리즘이 나오지 않는다. 그리디가 최적이 아니라는것을 보여주는 예시가 0/1 knapsack 알고리즘이다.

 

 

 

2) 만약에 1,2번 물건만 고려했을 때 2번을 불포함시킨게 가치의 최대값이라서 2번을 배낭에 안담았는데, 1,2,3,4번을 다 고려했을 때 2, 4번이 최대값이면 어떡함?

: 반례가 될만한 경우를 찾아볼때 이해할 수 있다.

 

Example)
9kg의 배낭을 채워야 하고
1번 배낭: 6kg, 13원
2번 배낭 : 4kg, 8원
3번배낭: 3kg, 6원
4번배낭 : 5kg, 15원 일 경우를 생각해보자.

Q) 이때 1,2번배낭 만을 고려했을 때에는 2번을 제외하고 1번의 배낭만 넣는게 최적의 값이다.

그러나 1, 2, 3, 4번을 모두 고려했을 때에는 2,4번 배낭을 넣는게 최적의 값이다. 그럼, 앞서 2번을 불포함시킨 경우는 어떡할건데?

 

A) 위의 예시에서 4번을 배낭에 담았을 때 남은 4kg을 채워야 한다. 따라서 3번 물건까지로 4kg를 채우는 dp[3][4]의 경우를 찾아야 하는데, 이때 알아서 2번 물건이 포함된 값이 최대 가치값으로 들어간다.

이때 앞서 어떤 조합으로 배낭을 채웠는진 중요하지 않다. dp를 통해 나머지 물건을 어떻게든 조합해 남은 무게를 채운 최대 가치값이 미리 저장되어있다.

-> 현재 가방의 무게에서 지금 탐색하는 i번째 물건을 넣는게 최적인지,불포함하는게 최적인지만 따져서 생각하자!