부분 배낭 문제 (Fractional Kanpsack Problem)

부분 배낭 문제 (Fractional Kanpsack Problem)

• 배낭 문제

  • n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대의 가치를 갖도록 넣는 방법에 대한 문제이다.

• 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다.

---

알고리즘

• 물건을 부분적으로 담을 수 있으므로, 단위 무게당 가치가 제일 높은 것부터 배낭에 넣는다.

  • 만약 통째로 넣을 수 없다면, 넣을 수 있는 만큼만 부분적으로 넣는다.

• 입력으로 각 물건의 무게와 가치, 배낭의 용량을 받는다.

• 출력은 배낭에 담은 물건 리스트와 배낭에 담은 가치의 총합이다.

  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;
  }

---

시간 복잡도

• 각 물건의 단위 무게당 가치를 계산할 때 O(n) 시간이 걸린다.

• 정렬할 때 O(nlogn) 시간이 걸린다.

• 반복문에서 최대 O(n) 시간이 걸린다.

• 따라서 시간 복잡도는 O(nlogn)이다.

---

0-1 배낭 문제

• 부분 배낭 문제의 원형이다.

• 0/1 배낭 문제라고도 표기한다.

  • 0은 물건을 배낭에 넣지 않는다는 뜻이고, 1은 넣는다는 뜻이다.

• 그리디 알고리즘으로 해결할 수 없고, 다음 알고리즘들로 해결 가능하다.

  • 동적 계획(Dynamic Programming) 알고리즘

  • 백트래킹(Backtracking) 기법

  • 분기 한정(Branch-and-Bound)