냅색(배낭) 알고리즘

배낭 문제

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데,

짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem),

짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.

 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

배낭 문제 - 위키백과, 우리 모두의 백과사전

 

알고리즘

• x축에 가방의 무게 (1~K), y축에 물건의 개수(N) 크기의 2차원 배열을 만든다.
• knapsack[i][j] 값을 순서대로 채워나간다.
  • 현재 위치(j)에서 가능한 가방의 최대 무게가 현재 물건의 무게(weight)보다 작다면, [이전 물건][같은 무게] 위치의 값을 가져온다.
  • 아니라면, (현재 물건의 가치 + 현재 물건을 넣은 뒤 여유 공간에 넣을 수 있는 무게의 가치) , (다른 물건으로 채우는 무게의 가치) 두 값 중 최댓값을 가져온다.

수식

knapsack[i][j] = max(현재 물건의 가치 + knapsack[이전물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전물건][현재 가방 무게])

knapsack[i][j] = max(value + knapsack[i-1][j-weight], knapsack[i-1][j])

		0	1	2	3	4	5	6	7
weight	value
6	13		0	0	0	0	0	13	13
4	8		0	0	0	8	8	13	13
3	6		0	0	6	8	8	13	14
5	12		0	0	6	8	12	13	14

 

예제

백준 12865번 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

코드

N, K = map(int, input().split())
arr = [[0,0]]
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for _ in range(N):
    arr.append(list(map(int, input().split())))
    
for i in range(1,N+1):
    for j in range(1,K+1):
        weight = arr[i][0]
        value = arr[i][1]
        
        if j < weight:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(value + knapsack[i-1][j-weight], knapsack[i-1][j])
            
print(knapsack[N][K])