[Algorithm] 냅색 알고리즘 (Knapsack Algorithm)

배낭문제(Knapsack) - 냅색 알고리즘의 경우 짐을 쪼갤 수 있냐 없냐로 나뉜다.

짐을 쪼갤 수 있는 경우를 Fractional Knapsack Algorithm

그 반대의 경우를 0-1 Kanpsack Algorithm이라고 한다.

 

1. Fractional Knapsack

• 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 정렬
• 남은 배낭이 감당할 수 있는 무게보다 < 물건의 무게가 많이 나가면 잘라서 넣으면 된다.
• Greedy로 해결 가능!!

사용하기 쉬운 알고리즘이라 따로 코드는 없고 개념만 보자면

 

1. 각각 부피가 1 2 3, 단가가 3, 2, 1 인 금반지, 은반지, 동반지가 있을 때 여유공간이 4인 배낭이 존재한다.
2. 이 때, 각 반지의 단가 / 부피를 해준 후 값이 높은 순으로 정렬해준다.
3. 이후, 여유 공간에 가격이 비싼 순서로 담아주면 된다.

 

2. 0-1 Knapsack

• 물건을 자를 수 없기 때문에 물건의 무게, 가격, 배낭의 남은 용량을 모두 고려하여야 한다.
• 예시로 -> 15kg의 여유공간에 아래와 같은 물건 3개를 골라 담을 때 최대 가치를 구하여라!
  • [물건 A] 가치: 10, 무게: 13kg
    [물건 B] 가치: 6, 무게: 6kg
    [물건 C] 가치: 5, 무게: 6kg
• 그리디로 풀 경우 물건 A를 담고 끝나지만
• A를 Pass하고 B와 C를 담는 것이 최고의 가치를 담을 수 있다.

 

따라서, 그리디가 아닌 DP를 이용해서 풀어준다.

• 가방에 최대 M kg 까지 담을 수 있을 때,
• dp[i][j] = 가방에 담은 물건의 무게 합이 i일 때, 처음 j개의 물건 중 담을 수 있는 최대 가치 ( 1 < i <=M)
  1. i가 현재 물건의 무게 w보다 작을 때
     • 현재 물건을 담을 수 없으므로 이전의 값 복사
     • dp[i][j] = dp[i][j-1]
  2. i가 현재 물건의 무게 w와 같거나 클 때
     • 현재 물건을 담을 수 있다.
     • 물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당해준다.
     • 현재 물건의 가치는 v 이다.
     • dp[i][j] = max( dp[i][j-1] , dp[i-w][j-1] + v)
  3. dp[가방 크기][물건의 수] 로 구해줄 수 있다.

 

예시 코드 - 더보기 클릭

def knapsack1(capacity, n):
    array = [[0 for _ in range(capacity+1)] for _ in range(n+1)]
    for i in range(1, n+1):
        for s in range(1, capacity+1):
            if size[i-1] > s:  # 물건의 부피가 s보다 크면
                array[i][s] = array[i - 1][s]
            else:  # 물건의 부피가 s보다 작거나 같으면
                array[i][s] = max(value[i-1] + array[i-1][s-size[i-1]], array[i-1][s])
            print('%2d' % array[i][s], end=' ')
        print()
    return array[n][capacity]


size = [9, 3, 4, 7, 8]
value = [13, 4, 5, 10, 11]
print(knapsack1(10, 5))