[백준] 12865번 평범한배낭 풀이 (중복미허용 냅색)

www.acmicpc.net/problem/12865

# 요약

동적 계획법(Dynamic Programming) 대표 유형 문제입니다.

Dynamic 테이블을 만들어 물품별로 업데이트를 진행해서 풀 수 있습니다.

N : 상품수, K : 최대 무게 일 때 복잡도는 O(N*K)

동적 계획법을 쓰지 않고 모든 경우의 수로 문제를 풀려고 하면 O(N^2)

# 문제풀이

Dynamic 테이블 업데이트 과정을 엑셀로 정리해봤습니다.

이번 문제에서 핵심은 2가지입니다.

 

1. 동적 계획법 활용 (다이나믹 테이블 사용)

2. 중복 미허용이므로 각 상품별 Dynamic 테이블 업데이트 시 오른쪽에서 왼쪽으로 업데이트 (←)

• 중복을 허용한다면 각 상품별 왼쪽에서 오른쪽으로 Dynamic 테이블 업데이트 (→)

다이나믹 테이블 업데이트 과정

# 코드

''' 중복 미허용 냅색 예시 '''

N, K = 4, 9
m = [(6, 13), (4, 9), (3, 8), (5, 11)]

# 다이나믹 테이블
dy = [0]*(K+1)

# 다이나믹 테이블 업데이트
for i in range(N):
    w = m[i][0]
    v = m[i][1]
    for j in range(K, w-1, -1):
        dy[j] = max(dy[j-w] + v, dy[j])

print(dy)
print(max(dy))

[0, 0, 0, 8, 9, 11, 13, 17, 19, 21]
21


''' 중복 허용 냅색 예시 '''

N, K = 4, 9
m = [(6, 13), (4, 9), (3, 8), (5, 11)]

# 다이나믹 테이블
dy = [0]*(K+1)

# 다이나믹 테이블 업데이트
for i in range(N):
    w = m[i][0]
    v = m[i][1]
    for j in range(K, w-1, -1):
        dy[j] = max(dy[j-w] + v, dy[j])

print(dy)
print(max(dy))

[0, 0, 0, 8, 9, 11, 16, 17, 19, 24]
24

# 중복 허용 냅색 문제 예시 (백준 알고리즘 4781번 사탕가게)

www.acmicpc.net/problem/4781