연속 배낭 문제

Continuous knapsack problem

이론 컴퓨터 과학에서 연속 배낭 문제(분수 배낭 문제라고도 한다)는 결합 최적화에서 알고리즘적인 문제로, 컨테이너("캡삭")를 선택한 다른 재료의 일부분으로 채워 선택된 값을 최대화하는 것이 목표다.[1][2]그것은 컨테이너에 넣을 아이템들이 분리될 수 없는 전형적인 배낭 문제와 유사하지만, 전통적인 배낭 문제는 NP-hard인 반면, 연속적인 배낭 문제는 다항 시간 내에 해결될 수 있다.[1]그것은 문제의 형성에 있어 겉보기에는 작은 변화가 어떻게 계산 복잡성에 큰 영향을 미칠 수 있는지를 보여주는 전형적인 예다.

문제 정의

연속적이거나 고전적인 배낭 문제의 예는 배낭의 숫자 용량 W와 함께 재료 모음으로 명시될 수 있으며, 각각은 선택할 수 있는 재료의 무게i w와 해당 재료의 총 값i v라는 두 개의 번호를 가지고 있다.목표는 용량 제약에 따라 각 재료의 양 xi ≤ w를i 선택하는 것이다.

그리고 총 유익성 극대화
전형적인 배낭 문제에서, x의i 각 양은 0 또는 w여야i 한다; 연속적인 배낭 문제는 x가i 0에서 w까지i 연속적으로 범위를 허용함으로써 다르다.[1]

이 문제의 일부 공식은 변수 x의i 크기를 0부터 1까지로 재조정한다.이 경우 용량 제약 조건이

그리고 목표는 총 이익을 최대화하는 것이다.

솔루션 기법

계속되는 배낭 문제는 조지 단치히가 1957년에 처음 발표한 탐욕스러운 알고리즘으로 해결할 수 있는데,[2][3] 이 알고리즘은 단위 무게당 값에 따라 재료를 정렬된 순서대로 고려한다.각 재료에 대해 x의i 양은 가능한 한 큰 값으로 선택된다.

  • 지금까지 선택한 값의 합이 용량 W와 같다면 알고리즘은i x = 0을 설정한다.
  • 지금까지 선택한 값의 합과 W의 차이가 w보다i 작으면 알고리즘은 xi = d를 설정한다.
  • 나머지 경우 알고리즘은i x = w를i 선택한다.

재료를 정렬할 필요성 때문에 이 알고리즘은 n 재료로 입력하면 O(n log n) 시간이 걸린다.[1][2]그러나 가중치 있는 중위수를 찾기 위한 알고리즘을 적용함으로써 시간 O(n)로 문제를 해결할 수 있다.[2]

참조

  1. ^ a b c d Goodrich, Michael T.; Tamassia, Roberto (2002), "5.1.1 The Fractional Knapsack Problem", Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, pp. 259–260.
  2. ^ a b c d Korte, Bernhard; Vygen, Jens (2012), "17.1 Fractional Knapsack and Weighted Median", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21, Springer, pp. 459–461, ISBN 9783642244889.
  3. ^ Dantzig, George B. (1957), "Discrete-variable extremum problems", Operations Research, 5: 266–277, doi:10.1287/opre.5.2.266, MR 0089098.