5.9 0-1 배낭 - 재귀

그 이름도 유명한 배낭 문제. (https://www.acmicpc.net/problem/12865)
간단히 문제를 설명하자면
무게, 가격을 나타내는 몇개의 쌍이 존재할 때
무게의 한도치가 정해진다면 최대값을 구하는 문제다.

일단 재귀를 사용해서 풀려면 아래의 두가지 경우의 반복이라고 볼 수 있다.
물건이 n개 있다고 할 때, n번 물건을 선택한다면
1. 물건을 배낭에 넣을 때 : 남은 물건의 갯수는 n-1, 배낭에 추가로 넣을 수 있는 최대 무게는 C - weight[n-1]이 됨. 물건의 가치는 value[n-1]만큼 증가. 결국 n-1개의 물건과 C - weight[n-1]의 배낭이 있는 문제로 원래 문제와 동일한 형태가 된다.
2. 물건을 배낭에 넣지 않을 때 : 물건은 n-1개, 배낭에 추가가 가능한 최대 무게는 C. 결국 n-1개의 물건과 C의 무게를 넣을 수 있는 배낭 문제와 동일.
종료조건 : 남은 물건이 없거나 배낭이 꽉 찼을 때
위의 내용을 코드로 옮기면 다음과 같다.

import sys
sys.setrecursionlimit(10**5)

def solve(c, weight, value, n):
    if n <= 0 or c <= 0:
        return 0

    if weight[n-1] > c:
        return solve(c, weight, value, n-1)

    carry = value[n-1] + solve(c - weight[n-1], weight, value, n-1)
    leave = solve(c, weight, value, n-1)

    return max(carry, leave)

if __name__ == '__main__':
    n, c = map(int, input().split())
    weight = []
    value = []
    for _ in range(n):
        a, b = map(int, input().split())
        weight.append(a)
        value.append(b)

    print(solve(c, weight, value, n))

각 노드가 두개의 자식 노드를 가지고 있는 재귀 호출 구조를 갖고 있다.
결국 같은 하위 문제를 반복 계산하는 경우가 존재하므로 DP로 풀 수 있다.