[Algorithm] Knapsack

알고리즘 개념

특정 제한 조건 내에서 가장 높은 가치를 얻을 수 있는
선택 조합을 찾는 문제를 해결하기 위한 알고리즘

즉, 조합 최적화 문제의 일종

 

배낭문제가 대표적

 -  담을 수 있는 최대 무게가 정해진 배낭과 함께
    각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때,

    배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제

 

알고리즘 종류

이때, 주어진 아이템의 분할 가능 여부에 따라 두 종류로 나뉜다.

이번 블로그 글에서는 분할 불가한 0/1 Knapsack을 다룰 것이다.

알고리즘 종류	해결 방법	특징(아이템 분할 여부)
0/1 Knapsack	동적 계획법, 백트레킹	아이템 분할 불가
Fractional Knapsack	탐욕적 접근법	아이템 분할 선택 가능

1. 0/1 Knapsack Problem

- 아이템의 분할 선택이 불가하다.

 

해결 알고리즘 찾기

1) Brute Force - 효율적이지 않음

- 해당 조건에 맞는 부분 집합을 구하는 문제로 모든 부분 집합을 확인해 보면 답이 구해진다.

- 하지만, n이 큰 경우 $ 2^{n} $ 개의 경우의 수를 모두 확인해야한다.

- 이때, 시간복잡도는 $ O(2^{n}) $ 으로 효율적이지 않다.

 

2) 그리디(탐욕적 접근법) - 최적해 구할 수 없음

- 그리디(탐욕적 접근법)로는 최적해를 찾을 수 없다.

- 그리디 알고리즘은 아이템의 가치 대비 무게 비율(value/weight)이 가장 높은 것을 먼저 선택한다.

 

• 아이템이 부분적으로 선택될 수 없음
  Fractional Knapsack 문제에서는 아이템을 나누어 선택할 수 있기 때문에
  가치 대비 무게 비율이 높은 아이템을 우선적으로 선택하면 항상 최적해를 보장할 수 있다.
  하지만 0/1 Knapsack에서는 아이템을 통째로 담거나(1), 담지 않거나(0)의 선택만 가능하므로,
  가치 대비 무게 비율이 높은 아이템을 우선 선택하더라도 전체적으로 최적의 조합을 이루지 못할 수 있다.
• 작은 무게의 아이템이 전체 가치를 크게 높이는 경우를 놓침
  가치 대비 무게 비율이 낮더라도,배낭의 남은 용량에 딱 맞는 아이템이나 가치가 큰 아이템을
  포함시키는 것이 더 높은 전체 가치를 제공할 수 있다.
  그리디는 이러한 전체 조합을 고려하지 않는다.
• 예시)
  • 값이 비싼 물건부터 채우기
    조건 - (물건 1) 25kg, 10만원 / (물건 2) 10kg, 9만원 / (물건 3)10kg, 5만원
    탐욕적 방법 결과 -> (물건 1) 25kg, 10만원
    최적해 -> (물건 2, 물건 3) 20kg, 14만원
  • 가벼운 물건부터 채우기
    조건 - (물건 1) 25kg, 15만원 / (물건 2) 10kg, 9만원 / (물건 3)10kg, 5만원
    탐욕적 방법 결과 -> (물건 2, 물건 3) 20kg, 14만원
    최적해 -> (물건 1) 25kg, 15만원
  • 무게 당 값이 높은 순서로 채우기
    조건 - (물건 1) 5kg, 50만원 / (물건 2) 10kg, 60만원 / (물건 3) 20kg, 140만원
    탐욕적 방법 결과 -> (물건 1, 물건 3) 25kg, 190만원
    최적해 -> (물건 2, 물건 3) 30kg, 200만원

3) DP(동적 계획법) - 적합한 방법

 

- 모든 가능한 조합을 효율적으로 계산하여 최적의 선택을 제공하기 때문에
  주로 DP 방식을 통해 접근한다.

 

2. Fractional Knapsack Problem

- 아이템의 분할 선택이 가능하다.

- 배낭에 담을 수 있는 아이템 조합을 찾아
  가치 대비 무게 비율(value/weight)이 높은 순으로 담아 최대 가치를 얻는 것이 목표이다.

- 그리디(탐욕적 접근법)을 통해 접근

• 아이템을 가치 대비 무게 비율(v[i]/w[i]v[i]/w[i]v[i]/w[i])에 따라 내림차순 정렬
• 배낭에 아이템을 가능한 한 많이 넣음
• 더 이상 전체 아이템을 담을 수 없으면, 남은 공간만큼 아이템을 부분적으로 담음

 

알고리즘 구조

배낭에 담을 수 있는 아이템의 조합을 찾아 최대 가치를 얻는 것이 목표이다.

부분 집합으로 구하며

1) 해당 물건이 지금 배낭 조건 무게보다 큰 경우 넣을 수 없다.

조건 : w[i]>j

점화식 : dp[i][j] = dp[i−1][j]

2) 현재 아이템을 추가할 수 있는 경우, 아이템을 넣는 경우와 넣지 않는 경우 중 더 큰 값을 선택한다.

조건 : w[i]≤j

점화식 : dp[i][j] =  max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])

​

예시를 통한 알고리즘 흐름

​조건)

    weights = [2, 3, 4, 5]

    values = [3, 4, 5, 6]

    max_weight = 5

흐름)

 

1) 0과 1에는 무게 2인 물건을 담을 수 없으므로 가치가 0이다.

2) 2에는 무게 2인 물건을 담을 수 있으므로

    담는 것과 담지 않는 것을 비교한다. 

    이때는 담는 것이 더 가치가 높으므로 담는다. 가치는 3이다.

 

 

1) 무게가 3일 때, 무게가 3인 물건을 담을 수 있다.

    담는 것(4) : dp[i−1][j−w[i]]+v[i] -> dp[1][0] + 가치 4 

    담지 않는 것(3) : dp[i−1][j] -> dp[1][3]

    때문에 담는 것이 가치가 높으므로 무게가 2, 가치가 3인 물건을 빼고 

    무게가 3, 가치가 4인 물건을 담는다.

 

 

해당 방식을 통해 계속 표를 작성해가면 왼쪽과 같은 표가 완성된다.

이때, 총 무게가 5인 가방에 담을 수 있는 최대 가치는 

dp[n][최대 무게]이다.

코드

0/1 Knapsack Problem 코드

# 예시 코드

def knapsack_01(weights, values, max_weight):
    n = len(weights)
    dp = [[0] * (max_weight + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(max_weight + 1):
            if weights[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][max_weight]

# Example usage:
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_weight = 5
print(knapsack_01(weights, values, max_weight))  # Output: 7

 

+) Fractional Knapsack Problem 코드

def fractional_knapsack(weights, values, max_weight):
    n = len(weights)
    items = sorted([(values[i] / weights[i], weights[i], values[i]) for i in range(n)], reverse=True)
    total_value = 0

    for value_per_weight, weight, value in items:
        if max_weight >= weight:
            total_value += value
            max_weight -= weight
        else:
            total_value += value_per_weight * max_weight
            break

    return total_value

# Example usage:
weights = [10, 20, 30]
values = [60, 100, 120]
max_weight = 50
print(fractional_knapsack(weights, values, max_weight))  # Output: 240.0

 

참고

https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C

배낭 문제

https://jeonyeohun.tistory.com/86

[알고리즘 정리] 배낭 문제(Knapsack Problem)