[백준] 평범한 배낭 12865번 DP (python)

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

풀이 방법

일반적인 냅색 문제로 DP를 이용해서 풀이할 수 있다.

하지만 문제를 풀이할 때 엄청난 실수를 했다.

top-down 방식을 사용했는데 이를 잘 못 적용한 것이다.

DP의 핵심은 문제를 분리할 때 서로 영향을 받지 않아야 한다. 하지만 처음 코드는 서로가 영향을 받는 코드를 작성했다.

  

N, K = map(int, input().split())
arr = [[0, 0] for _ in range(N)]
dp = [[-1 for _ in range(100001)] for _ in range(N) ]
for i in range(N):
    arr[i][0], arr[i][1] = map(int, input().split())
def kanpSack(idx, weight, value): ## 현재, 현재 가방 무게(자기 걸 포함하는 지 안하는지)
    print(idx, weight, value)
    if (idx == N): ## 마지막 탈출 조건
        return value
    if (dp[idx][weight] != -1):
        return dp[idx][weight]
    ret = 0
    if weight + arr[idx][0] <= K: ## 현재 포함할 수 있는 경우
        ret = max(ret, kanpSack(idx+1, weight+arr[idx][0], value+arr[idx][1]))    
    ret = max(ret, kanpSack(idx+1, weight, value)) ## 현재 포함하지 않는 경우 
    dp[idx][weight] = max(ret, dp[idx][weight])
    return dp[idx][weight]
print(kanpSack(0,0,0))

위 코드에서 value는 이전 까지의이전까지의 선택한 value를 저장한다 이를 저장하며 다음 부분 문제로 넘어가기 때문에 이전까지의 선택에 영향을 받고 있었던 것이다. 즉 이렇게 함수를 작성하면 dp[idx][weight][value]와 같이 dp 배열을 수정해야 한다.

5 7
4 10
1 5
3 20
2 6
5 10

그래서 위와 같은 입력이 들어왔을 때

idx가 3이고 weight가 4인 경우가 (4, 10)을 선택하는 경우와 (1, 5), (3, 20)을 선택하는 경우 value가 다른데 (4, 10)을 선택했을 때로  메모리제이션이 된다. (4, 10)이 먼저 수행되기 때문에

 

이를 해결하기위해 문제를 완전히 분할했다.

N, K = map(int, input().split())
arr = [[0, 0] for _ in range(N)]
dp = [[-1 for _ in range(100001)] for _ in range(N) ]
for i in range(N):
    arr[i][0], arr[i][1] = map(int, input().split())

def kanpSack(idx, weight):
    print(idx, weight)
    if idx == N: 
        return 0
    if dp[idx][weight] != -1:
        return dp[idx][weight]
    # 현재 물건을 선택하지 않았을 때의 최대 가치
    not_selected = kanpSack(idx + 1, weight)
    # 현재 물건을 선택했을 때의 최대 가치
    selected = 0
    if weight + arr[idx][0] <= K:
        selected = arr[idx][1] + kanpSack(idx + 1, weight + arr[idx][0])
    # 선택 여부에 따라 최대 가치 반환
    dp[idx][weight] = max(not_selected, selected)
    return dp[idx][weight]

 

 

첫 번째 함수와 다른 점은 함수의 매개변수로 value를 제거했다. 이럼으로써 다음 분할 문제는 value의 영향을 받지 않게 되므로 dp알고리즘을 잘 수행할 수 있다.

 

다음에 적용할 것

• dp문제에서 문제를 나눌 때 이전의 영향을 받지 않아야 한다.
• top-down방식에서 함수의 인자는 dp배열에 다 포함되어야 한다.