5.9 0-1 배낭 - DP

DP로 풀기 위해서는 2차원 캐시 리스트를 하나 만들면 된다.
배낭의 용량이 j이고 i번째 물건까지의 최대 가격을 캐시로 저장하기로 한다.
1. i번째 물건을 선택하지 않았을 때 최대 가격 : cache [i-1][j]
2. i번째 물건을 선택했을 때 최대 가격 : value [i-1] + cache [j - weight [i-1]]
물건 i를 배낭에 넣으려면 배낭에는 j - weight [i-1]의 무게만큼만 들어있어야 하므로
물건 i의 가격에 이미 계산한 cache [j - weight [i-1]]의 값을 더하면 됨.

위의 내용을 코드로 옮기면 다음과 같다.

def solve_dp(c, weight, value, n):
    cache = [[0 for _ in range(c + 1)] for __ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, c + 1):
            if weight[i - 1] <= j:
                x = j - weight[i - 1]
                cache[i][j] = max(value[i - 1] + cache[i - 1][x], cache[i - 1][j])
            else:
                cache[i][j] = cache[i - 1][j]

    return cache[n][c]


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_dp(c, weight, value, n))

이번에 푼 DP도 2중 반복문의 사용으로 시간 복잡도는 최대 O(n^2)이다.
아직 이해하지 못한 부분이 좀 있어서.. 차후에 다시 한번 봐야 할 것 같다. ㅠㅠ