[알고리즘] 배낭 문제 (Knapsack Problem) - 부분 배낭 문제 (Fractional Knapsack)

배낭 문제는 한정된 배낭에 무게와 가치가 정해져있는 물건을 담을 때 담은 물건이 최대의 가치를 갖도록 물건을 정하는 문제이다

- n개의 물건 집합 S={1, 2, 3, 4,..., n} (물건번호)
- 배낭의 최대 무게 M
- 물건 i의 무게 w={w1, w2, w3,..., wi}
- 물건 i의 이윤 Pi

이렇게 있을 때

- ∑ wi*xi ≤ M (물건의 무게 총합 ≤ 배낭의 최대 무게) 
- ∑ Pi*xi => 최대 (물건 총합 가치 최대)

여야한다
여기서 xi의 범위에 따라 구현 방법이 달라지는데 두 가지 방법이 있다

1) xi 의 값이 0 ≤ xi ≤ 1 : 부분 배낭 문제
xi 가 1/3이라면 물건을 1/3 만큼 담는다는 얘기이다

- 그리디 알고리즘을 이용한다 (0-1 배낭문제보다 비교적 수월하다)

2) xi 의 값이 0 or 1 만 허용 : 0-1 배낭문제 
xi가 0일 때 > 물건을 담지 않는다
xi가 1일 때 > 물건을 담을 수 있다

- 동적 계획 알고리즘 (다이나믹 프로그래밍)을 이용한다

---

이번 글에서는 (1) xi 의 값이 0 ≤ xi ≤ 1 : 부분 배낭 문제 를 보도록 하자
예시를 통해 보면 더 쉬울것이다

 

①  xi 의 값이 0 ≤ xi ≤ 1 : 부분 배낭 문제

- 현재 배낭의 최대 무게 = 40그램
- 물건은 아래와 같다

 

(1) 단위 그램 당 가치를 구한다 

(2) 리스트 S에 단위 그램당 가치를 내림차순으로 정렬한다

(3)
- L = 배낭에 담을 물건 리스트
- w=0 (배낭의 담긴 물건 무게의 합)
- v=0 (배낭에 담긴 물건 가치의 합)

(4) S에서 단위 그램당 가치가 가장 큰 물건 x을 가져온다
(5)
- w + (x의 무게) ≤ 배낭 무게 한도 (C) 
- w = w + (x의 무게) / v= v+(x의 가치) / x를 S에서 제거

(6) 4,5번을 반복한다

(7) 배낭에 물건을 부분적으로 담을 여유가 있으면 ( if C-w > 0)
(8) 배낭에 담을 수 있는 물건(C-w) 만큼만 담는다

 

PSEUDO CODE

FractionalKnapsack(Item *arr, int capacity)
{

  각 물건의 단위 무게당 가치를 계산한다.
  단위 무게당 가치를 기준으로 내림차순 정렬하여 저장한다.
  
  int weight = 0; // 배낭에 담긴 무게
  int value = 0; // 배낭에 담긴 가치의 총합
  Item highest = 단위 무게당 가치가 가장 큰 물건;
  Item *list; // 배낭에 담긴 물건의 리스트
  
  while (weight + highest.weight <= capacity)
  {
    highest를 list에 추가한다.
    weight += highest.weight;
    value += highest.value;
    highest를 arr에서 제거한다.
    새로운 highest를 선정한다.
  }
  
  if (capacity > weight)
  {
    highest를 (capacity - weight)만큼만 list에 추가한다.
    value += capacity - weight;
  }
  
  return list, value;
}

 

시간복잡도

n개의 물건의 단위 그램당 가치를 계산하는 건 O(n)
물건의 그램 당 가치 계산 한 것을 정렬하는건 O(nlogn)
나머지 수행 시간은 O(1) 시간 소요된다

따라서 시간복잡도 : O(nlogn)