(BOJ)-12865, Python

문제 요약

출처: (BOJ)12865 - 평범한 배낭

$N$개의 물건이 있고, 각 물건의 무게($W$)와 가치($V$)가 주어진다. 물건을 배낭에 담을 때, 배낭의 최대 수납 무게($K$)를 초과하지 않으면서 얻을 수 있는 가치의 최대값을 구하는 문제이다.

• $1 ≤ N ≤ 100$

접근 과정

1. 완전탐색 접근(재귀)

물건을 선택하는 경우와 선택하지 않는 경우로 나누기 위해 재귀를 활용하여 접근하기로 했다. 결과는 시간초과였다.

코드 구현

N, K = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

def recursion(idx, weight, value):
    global max_value
    
    if weight > K:
        return 
    
    if idx == N:
        max_value = max(value, max_value)
        return 
    
    #상품 선택한 경우
    recursion(idx + 1, weight + items[idx][0], value + items[idx][1])
    #상품 선택안한 경우
    recursion(idx + 1, weight, value)

max_value = 0
recursion(0,0,0)
print(max_value)

2. DP 접근(메모이제이션)

시간 초과를 해결하기 위해 DP로 접근해보았다. 기본 아이디어는 이전 포스트를 참고하면 이해할 수 있다! 이번 문제에서는 무게도 생각해야 하므로, dp[idx][weight]처럼 2차원 리스트를 생성했다. 만약 인덱스만 생각하고 1차원 리스트를 생성한다면, 다음과 같은 문제가 발생할 수 있다.

주어진 문제의 예제 입력을 기준으로, idx == 0인 물건을 선택했을 경우와 선택하지 않았을 경우를 살펴보겠다.

• 물건을 선택한 경우: recursion(1, 13)
• 물건을 선택하지 않은 경우: recursion(1, 0)

두 경우 모두 dp[1]를 업데이트하게 되는데, 이렇게 하면 덮어쓰기 문제가 발생한다. 이러한 이유로, 두 경우 모두 고려할 수 있도록 dp[idx][weight]로 생성한 것이다.

코드 구현

• 인덱스만 고려할 경우

#로직 오류
N, limit_weight = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

def recursion(idx, weight):
    if weight > limit_weight:
        return -1e9
    
    if idx == N:
        return 0
    
    if dp[idx] != -1:
        return dp[idx]
    
    #상품 선택하거나 안한 경우 
    dp[idx] = max(recursion(idx + 1, weight + items[idx][0]) + items[idx][1], recursion(idx + 1, weight))
    print(dp[idx])
    return dp[idx]
    
dp = [-1  for _ in range(N)]

ans = recursion(0,0)
print(dp)
print(ans)

• 인덱스, 무게 모두 고려할 경우

#최종 코드
N, K = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

def recursion(idx, weight):
    if weight > K:
        return -1e9
    
    if idx == N:
        return 0
    
    if dp[idx][weight] != -1:
        return dp[idx][weight]
    
    #상품 선택하거나 안한 경우 
    dp[idx][weight] = max(recursion(idx + 1, weight + items[idx][0]) + items[idx][1], recursion(idx + 1,weight))
    
    return dp[idx][weight]
    
dp = [[-1 for _ in range(100_001)] for _ in range(N)]

ans = recursion(0,0)
print(ans)

회고

아무래도 이전 포스트에서 다뤘던 문제보다 $N$의 범위가 커지면서, 최대 $2^{100}$번의 연산을 해야 하므로 재귀 완전탐색 접근은 제한 시간 2초 내에 처리하기 무리였던 것 같다.