[boj] 평범한 배낭_12865

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

2차원 다이나믹 프로그래밍을 활용하는 대표적인 문제다.

 

원래는 '안녕_1535' 문제를 풀기 위해 먼저 풀어본 문제인데, 백트래킹을 이용한 재귀함수 호출로 풀려고 시도해봤지만 시간 초과로 통과하지 못했다. pypy3로도 안되더라.

 

처음 내가 시도했던 방법을 그림으로 그렸다. 물건이 A B C D 네 가지가 있다고 가정한 후 각 물건을 넣느냐, 마느냐를 모두 따지고, 무게가 초과되면 중간에 리턴시켜 백트래킹을 한다. 또, 모든 물건의 검사를 마치면서 결과 값이 현재 가지고 있는 결과보다 크다면 최대값으로 갱신해 이를 출력하려고 했다.

 

사실 아주 틀린 방법은 아니지만, 이런 방법으로 풀게 되면 시간초과 때문에 무슨 짓을 해도 통과할 수 가 없다.

때문에 다른 사람의 풀이를 참고하려고 유튜브 해설부터 블로그 포스팅을 싹싹 긁어 봤고, 이 문제의 바이블 처럼 여겨지는 블로그 포스팅이 있어 참고 할 수 있었다.

gsmesie692.tistory.com/113?category=523232

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

(그냥 이거 보세요.)

 

자세한 풀이는 위 블로그보다 잘할 자신이 없어 위 블로그를 보는 것을 추천한다. 그래도 나름대로 풀이를 요약하자면, 아래와 같이 적을 수 있을 것 같다.

 

이 문제는 2차원 다이나믹 프로그래밍을 이용해야 한다. dp[i][w]는 'i번째 물건 차례가 되었을 때 최대 w용량을 가진 배낭에서 얻을 수 있는 최대 이득' 이라는 의미를 가진다.

 

이후에 두 가지를 따져야 한다. 

1. i번째 물건을 배낭에 넣을 수 있는지?

2. (넣을 수 있다면) i번째 물건을 배낭에 넣을 것인지? 아니면 그냥 넘어갈 것인지?

 

1. i번째 물건이 배낭의 총 용량보다 크다면, 배낭 용량을 초과해 가져갈 수 없기 때문. 이 때에는 자명하게 i-1번째 최적값을 따라간다.

: dp[i][w] = dp[i-1][w]

 

2-1. 만약 i번째 물건을 넣지 않는다면 이 때 또한 i-1번째의 최적값을 따라갈 것이다.

2-2. 만약 i번째 물건을 넣는다면, i번째 물건이 남은 배낭의 용량 보다 클 수 있으므로 'i번째 물건의 용량만큼 용량을 확보했을 때의 최대값 + i번째 물건의 가치' 를 따져야 한다. 그리고 이것을 2-1과 비교해 더 큰 값으로 골라야 한다.

: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

(dp[i-1][w]는 i번째 물건을 넣지 않았을 때의 최대값, dp[i-1][w-weight[i]] + value[i]는 물건을 넣었을 때의 최대값이다. i번째 물건을 넣었을 때에는 i번째 물건의 가치가 더해지고, 최대값을 구하기 위해서는 i번째 물건의 무게만큼 배낭의 용량이 적을 때의 최대값에 더해야 하기 때문에 dp[i-1][w-weight[i]]에 value[i]를 더한다.)

 

필자는 오개념을 가지고 있어서 상당한 시간을 낭비했는데, 바로 i번째 물건을 넣을지 말지 판별할 때, i번째 물건의 무게와 '배낭의 남은 용량'을 비교했다.

 

2번을 따질 때에는 배낭에 물건을 넣을 수 있기 때문에 '배낭의 총 용량'과 물건의 무게를 비교 해야 한다. 그러나 필자는 이를 '배낭의 남은 용량'과 비교했고, max를 통해 선택을 하면 당연히 넣는 쪽이 가치가 높기 때문에 식이 이상하다고 생각하는 오개념을 가지고 있었다.ㅠㅠ

 

혹시나 필자같은 바보같은 시행착오를 겪는 사람은 거의 없겠으나... 만약 이 글을 본다면 '배낭의 남은 용량이 아닌 총 용량'과 i번째 물건의 무게를 비교해야 함을 명심하자.ㅠㅠ

 

배낭의 총 용량과 물건의 무게를 비교한다고 생각하는 경우가 이전의 물건을 빼고 i번째 물건을 넣었을 때 더 가치가 큰 경우까지 포함할 수 있다.

 

요약하자면 그냥 삽질을 크게 했다.

 

• 2차원 다이나믹 프로그래밍을 이용한 풀이(통과)

평범한 배낭 https://www.acmicpc.net/problem/12865

N, K = map(int, input().split())

weight = [0]
value = [0]
result = 0
cur = 0

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

for _ in range(N):
    W, V = map(int, input().split())
    weight.append(W)
    value.append(V)

for i in range(1, N+1):
    for w in range(K+1):
        if weight[i] <= w:
            graph[i][w] = max(graph[i-1][w], graph[i-1][w-weight[i]]+value[i])
        else:
            graph[i][w] = graph[i-1][w]

print(graph[N][K])

 

• 백트래킹과 재귀함수 호출로 시도한 풀이(시간초과)

# 평범한 배낭 https://www.acmicpc.net/problem/12865

N, K = map(int, input().split())

weight = []
value = []
result = 0

for _ in range(N):
    W, V = map(int, input().split())
    weight.append(W)
    value.append(V)

def Recursion(idx, lim, val):
    global result
    
    # 현재 배낭의 무게보다 많이 나가면 재귀 종료
    if lim > K:
        return
    if idx == N:
        if val > result:
            result = val
        return

    # i번째 물건을 선택함
    Recursion(idx+1, lim+weight[idx], val+value[idx])
    # i번째 물건을 선택하지 않음
    Recursion(idx+1, lim, val)

Recursion(0, 0, 0)
print(result)