[DP] BOJ_12865 평범한 배낭 ( 0-1 knapsack problem)

나는 DP를 좋아한다.
수험생때 수열을 아주 많이 공부했는데 그때 생각이 나는것같아서 마음이 편해진다.

알고리즘 수업들을때 이후로 dp문제를 아주 오랜만에 풀어봤는데 dp의 상징인 0-1 knapsack problem을 풀어보았다.

dp에 대한 감을 찾고자 여러가지 방법을 다른 사람의 코드도 참조하면서 풀어보았다.

recursive method

속도가 iterative하게 구현한 것보다 빨랐지만 메모리는 더 차치했다. 구현하기가 쉬웠고 코드도 간편했다.

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

W = []
V = []
# 2^N 을 막기위한 캐시 만들기 ( 중복된 경로를 가지 않게함)
# [idx][W]
dp_cache = [[0 for w in range(100001)] for idx in range(101)]

# dp(현재 위치, 현재 값)
def dp(i, w):
    # 다 돌았을때 종료
    if dp_cache[i][w] > 0:
        return dp_cache[i][w]
    if i == N:
        return 0

    v1 = 0
    if W[i] + w <= K:
        v1 = V[i] + dp(i+1, w+W[i])
    v2 = dp(i+1, w)
    result = max(v1, v2)
    dp_cache[i][w] = result
    return result

for i in range(0, N):
    w, v = input().split()
    w = int(w); v = int(v)

    W.append(w)
    V.append(v)

result = dp(0, 0)
print(result)

dp에 대한 감을 찾고자 유튜브 강의를 보고 따라치면서 이해했다.

iterative method

1) 일단 저장공간은 버린 방법

# [DP] 평범한 배낭

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

# [idx][W]
dp = [[0 for w in range(K+1)] for idx in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split())

    # 가방의 한계
    for acc_w in range(1, K+1):
        if acc_w < w:
            dp[i][acc_w] = dp[i-1][acc_w]
            continue
        dp[i][acc_w] = max(dp[i-1][acc_w], dp[i-1][acc_w - w] + v)

print(dp[N][K])

이건 내가 존경하는 Abdul Bari 센세의 knapsack 강의를 보고 그대로 구현한것이다.

n개의 물건 갯수 X 최대무게 w 만큼 2차원 배열을 만들고 value값을 나오는 족족 저장하는 방식여서 메모리가 아주 괴랄했다.

2) 이전 단계랑 지금 단계만 저장하자

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

dp = [[0 for _ in range(K+1)] for _ in range(2)]

for i in range(1, N+1):
    dp[0][:] = dp[1][:]
    w, v = map(int, input().split())

    dp[1][1:w] = dp[0][1:w]

    # 가방의 한계
    for limit in range(w, K+1):
        dp[1][limit] = max(dp[0][limit], dp[0][limit - w] + v)
print(dp[1][K])

---

이렇게 0-1 knapsack problem을 풀어보면서 dp를 연습했다. 알고리즘을 아주 오랫동안 안하다가 코테를 앞두고 부랴부랴하다보니까 큰일났다.