[Algorithm/DP] 0/1 Knapsack Problem (배낭 문제)

 

0/1 Knapsack Problem이란?

 

< 주어지는 조건 >

용량이 W인 배낭, N개의 물건(각 물건은 무게(w)와 가치(v)가 주어짐)

 

1. 배낭에 담을 물건의 무게의 합이 W를 초과하지 않으면서

2. 담을 수 있는 최대 가치를 찾는다.

 

물건을 쪼갤 수 있다면 > Fraction Knapsack Problem

물건을 쪼갤 수 없다면 > 0/1 Knapsack Problem

 

 

 

 

---

접근법

 

DP 중에서도 작은 문제의 해로 큰 문제의 해를 찾는 상향식 접근법을 사용한다.

그렇다면 점화식을 구해야 한다.

 

부분 문제를 정의해 보면,

물건을 담을 수 있는 경우와 담을 수 없는 경우로 나눌 수 있고

담을 수 있는 경우에는 물건을 넣기로 결정하거나 물건을 안 넣기로 결정하는 경우로 또 나눌 수 있다.

 

정리하면,

1. 물건을 담을 수 없는 경우 --> 현재가 i번째라고 했을 때, i-1번째까지의 가치를 그대로 들고 오면 됨

2. 물건을 담을 수 있고, 넣기로 결정 --> i-1번째까지의 가치와 현재 가치를 더한 값을 저장

3. 물건을 담을 수 있고, 안 넣기로 결정 --> i-1번째까지의 가치를 저장

 

물건을 담을 수 있는 경우는 2번과 3번 중 큰 값을 저장하면 된다.

 

 

 

 

---

코드

 

0/1 Knapsack의 대표 문제인 백준 12865 평범한 배낭 문제의 Python 코드를 들고 왔다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
backpack = [list(map(int, input().split())) for _ in range(n)]
zero = [[0, 0]]
bp = zero + backpack

dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(1, n+1):
    for w in range(k+1):
        if bp[i][0] > w: # 못넣는 상황
            dp[i][w] = dp[i-1][w]
        else: # 넣는 상황
            dp[i][w] = max(bp[i][1] + dp[i-1][w - bp[i][0]], dp[i-1][w])

print(dp[n][k])

< 변수 간략 설명 >

- zero를 더해준 이유는 배열의 i-1번째를 사용하기 때문에 IndexError를 막기 위해 임의로 0번째 물건을 추가해 주었다.

- bp배열은 [0]번째에 무게, [1]번째에 가치가 들어온다.

- dp배열은 n*k 크기의 2차원 배열이다.

 

 

위에서 정리했던 부분 문제를 들고 오면,

 

1. 물건을 담을 수 없는 경우
--> 이 물건의 무게(bp[i][0])가 현재 무게한도(w)를 넘어설 때 못 넣음. 무조건 dp[i-1][w] 저장.

 

2. 물건을 담을 수 있고, 넣기로 결정

3. 물건을 담을 수 있고, 안 넣기로 결정

--> 이 물건의 무게(bp[i][0])가 현재 무게한도(w) 이하일 때 넣을 수 있음. 

현재 가치 + i-1번째까지의 가치(bp[i][1] + dp[i-1][w - bp[i][0]])와 i-1번째까지의 가치인 dp[i-1][w] 중 큰 값 저장

 

이렇게 해서 마지막까지 물건을 다 담아봤을 때의 최적해를 출력하면 답이 나온다.

 

 

 

 

---

 

대표적인 0/1 Knapsack 문제

12865번: 평범한 배낭

SW Expert Academy