[백준/python] DP 유형 - 배낭(Knapsack) 문제

DP 유형으로 종종 언급되는 배낭 문제 (knapsack) 유형에 대해 알아 봅시다.

---

0 / 1 Knapsack

 

담거나 담지 않거나

코드트리 #Knapsack, 배낭문제 (보석 무게, 가격을 고려한 최대 가치 만들기) 백준 #12865 평범한 배낭 (기본); 시간복잡도 O(N*K) 백준 #10844 쉬운 계단 (풀어봐야함) 백준 #2629 양팔문제 (응용)

2D 배열로 풀기; dp[i][w] = i번째 물건까지 사용해서 w무게를 갖는 최대 가치

 

 

import sys
readline = lambda: sys.stdin.readline().strip()

# 전처리
N, TARGET_WEIGHT = map(int, readline().split())
bag = [(0, 0)]  # empty item


for _ in range(N):
    w, v = map(int, readline().split())
    bag.append((w, v))

WEIGHT = 0
VALUE = 1

# dp[i][w] = i번째 물건까지 사용해서 w무게를 갖는 최대 가치
dp = [[0 for _ in range(TARGET_WEIGHT + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for w in range(1, TARGET_WEIGHT + 1):
        cur_weight = bag[i][WEIGHT]
        cur_value = bag[i][VALUE]

        if w >= cur_weight:  # 과거값으로부터 갱신 가능
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - cur_weight] + cur_value)
        else:  # 과거값 그대로 갱신
            dp[i][w] = dp[i - 1][w]

print(dp[N][TARGET_WEIGHT])

 

 

1D 배열로 풀기; dp[i]

 

import sys
readline = lambda: sys.stdin.readline().strip()

# 전처리
N, TARGET_WEIGHT = map(int, readline().split())
bag = []
for _ in range(N):
    w, v = map(int, readline().split())
    bag.append((w, v))

# dp[w] = w 무게에서 최대 가치
dp = [0] * (TARGET_WEIGHT + 1)

WEIGHT = 0
VALUE = 1

for i in range(N):
    for w in range(TARGET_WEIGHT, -1, -1): # TODO: 역순부터 채워야하는 이유는 코인유형 궁금증과 함께 해결
        cur_weight = bag[i][WEIGHT]
        cur_value = bag[i][VALUE]
        if w - cur_weight >= 0:  # 유효한 인덱스 체크
            dp[w] = max(dp[w], dp[w - cur_weight] + cur_value)

print(dp[TARGET_WEIGHT])

 

 

#12920 평범한 배낭 2

Q. 보석 개수가 중복일 수 있다? 그럼 #12865 보석함에 여러번 넣어주면 되는거 아닌가? A. 그러면 O(NKM) 복잡도를 갖게됨 Q. 비트마스킹으로 O(NKM) 시간복잡도를 O(N*logK*M) 으로 줄일 수 있다.

 

 

 

Fractional Knapsack

 

쪼개어 담을 수 있다면

 

보석 문제에서 쪼갤 수 있다면, 무게 대비 가치가 높은 보석을 우선적으로 담으면 됨. 

곧 그리디 알고리즘

 

(관련 백준 문제는 찾으면 추가 예정)