배낭 문제 (0/1 Knapsack Problem)

코딩 테스트를 치르다가 배낭 같아보이는 문제를 만났지만 손도 못 대고 시험이 끝나버렸다. 배낭 알고리즘을 이해만 하고 넘어갔지, 직접 풀어본 적이 없었던 것 같다. 그래서 문제 몇 개를 직접 풀어보며 복습했다. 회고를 위해 이 글을 작성한다.

배낭 문제란?

배낭 문제(Knapsack Problem)는 다음과 같은 상황을 가정하는 문제이다.

• N개의 물건이 있다.
• 각 물건은 특정한 무게(W)와 가치(V)를 가진다.
• 최대 K 무게까지 담을 수 있는 배낭이 있다.
• 배낭에 담을 수 있는 물건의 조합 중에서 가치의 합이 최대가 되도록 한다.

점화식

일반적으로 점화식은 이러한 형태다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

2차원 DP로 해결하기

문제: 백준 12865번 - 평범한 배낭

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

W = [0 for _ in range(N+1)]  # 무게
V = [0 for _ in range(N+1)]  # 가치
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

# dp[i][j]: i번째 물건까지 고려하고, j무게까지 담을 수 있을 때 최대 가치
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]  

for i in range(1, N+1):
    for j in range(1, K+1):
        if j >= W[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][K])

• 시간복잡도: O(NK)
• 공간복잡도: O(NK)

1차원 DP로 최적화하기

위 코드에서는 2차원 DP 배열을 사용했지만, 사실 1차원 배열만을 사용해서 풀 수도 있다. 값을 계산할 때 바로 이전 행인 dp[i-1][j]만 사용되고, 그보다 더 이전 행의 값은 사용되지 않으므로 계속 기억하고 있을 필요가 없다는 점을 이용한다. 다만 dp[i-1][j-W[i]]를 참조할 때 이 값은 갱신되기 전 값을 사용해야 하므로 갱신을 뒤에서부터 해야 한다.

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

W = [0 for _ in range(N+1)]  # 무게
V = [0 for _ in range(N+1)]  # 가치
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

# 1차원 DP 배열 사용
dp = [0 for _ in range(K+1)]

for i in range(1, N+1):
    for j in range(K, 0, -1):
        if j >= W[i]:
            dp[j] = max(dp[j], dp[j-W[i]] + V[i])

print(dp[K])

• 시간복잡도: O(NK)
• 공간복잡도: O(K)

같은 방법으로 비슷한 문제를 한 개 더 풀어봤다. 문제: 백준 7579번 - 앱

# 세로로 앱 정보: (바이트, 비용)
# 가로로 비용

# i : 앱 번호
# dp[j] = j비용으로 확보할 수 있는 최대 바이트
N, M = map(int, input().split())
A = [0] + list(map(int, input().split()))  # 바이트 수
C = [0] + list(map(int, input().split()))  # 비용

dp = [0 for _ in range(sum(C) + 1)]

# 점화식
# dp[j] = max(dp[j], dp[j - C[i]] + A[i])
for i in range(1, N+1):
    for j in range(sum(C), -1, -1): # 뒤에서부터 갱신
        # 이 앱의 비용이 j비용보다 작거나 같을 때에만 이 앱을 고려할 수 있음
        if j >= C[i]:
            dp[j] = max(dp[j], dp[j - C[i]] + A[i])
    # print(dp)

# 처음으로 M바이트 이상 확보할 수 있는 지점을 출력
for i in range(sum(C) + 1):
    if dp[i] >= M:
        print(i)
        break

1 ≤ M ≤ 10,000,000 이라서 cost를 기준으로 배열을 만들어야 한다.

기타 생각

시험에서 만났던 문제는 N과 K의 범위가 매우 컸다. 마지막 문제였던 만큼 O(NK)로 푸는 것보다 더 효율적인 정답이 있었을 거 같다(배낭 문제가 아닐 수도 있다)

+) 오픈채팅방에서 확인해보니 그리디 + 우선순위 큐(priority queue) 를 활용하여 푸는 게 가장 빠르다고 한다 😅

참고

• [Java]배낭 문제(Knapsack Problem)