선형 시간의 분수 배낭

문제를 말씀하시면 좋을 것입니다. $ n $ 항목이 $ x_i $ 이고 각각 수익이 $ p_i $ 및 체중 $ w_i $ . 총 중량이 최대 $ W $ 라는 제약 조건 하에서 수익을 극대화하려고합니다. 각 항목 $ x_i $ 에 대해 분수 $ \ theta \ in [0,1] $ , 수익 $ \ theta p_i $ 및 무게 $ \ theta w_i $ .

다음은 예입니다. 순금은 수익이 $ 1000 $ 이고 무게는 $ 1 $ 입니다. 수익이 $ 1 $ 이고 무게가 $ 10 $ 인 바나나도 있습니다. $ 2 $ 의 무게를 지닐 수 있다고 가정합니다. 당신은 무엇을 하시겠습니까? 당연히 먼저 가능한 한 많은 금을 넣습니다. 즉, 모든 것을 넣은 다음 가능한 한 많은 바나나를 넣습니다. 즉, 10 분의 1을 총 수익으로 $ 1000.1 $ .

일반 알고리즘은 비슷합니다. $ W $ 를 가장 많이 채울 $ 1000 $ “슬롯”으로 나눈다 고 가정합니다. 수익성있는 품목-무게의 부분 $ W / 1000 $ . 무게가 $ w_i $ 인 항목의 경우 $ w_i / (W / 1000) $ 개가 있습니다 (가정 이 값은 정수)이며 각각의 가치는 $ p_i / (w_i / (W / 1000)) $ 입니다. 슬롯에 넣을 항목을 선택할 때 수익을 극대화하고 싶으므로 최대 $ p_i / w_i $ 가있는 항목을 선택하고 최대한 많이 넣습니다. 가능한 한 조각. 다 떨어지면 다음으로 큰 $ p_i / w_i $ 등의 항목을 선택합니다.

나누지 않고 구현할 수 있습니다. $ W $ 를 $ 1000 $ 조각으로 : 최대 $ p_i / w_i $ , 최대한 많이 넣으세요. 다 떨어지면 다음을 선택하고 가능한 많이 넣으십시오. 등등. 이 알고리즘을 구현하려면 $ p_i / w_i $ 목록을 정렬해야합니다.이 작업에는 시간이 소요됩니다. $ O (n \ log n) $ . 설명하는 알고리즘은 알고리즘을 무작위 화하는 대신 실행 시간을 $ O (n) $ 로 줄이기 위해 quickselect에서 동일한 트릭을 사용합니다.

알고리즘을 이해하려면 다음 경로를 제안합니다.

1. 분수 배낭에 대한 고전적인 탐욕스러운 알고리즘을 이해합니다.
2. 빠른 선택을 이해합니다.
3. 인용 한 알고리즘이 빠른 선택 기술과 탐욕스러운 접근 방식을 결합하는 방법을 확인하세요.

R 은 모든 물체의 이익 / 무게 비율의 집합 으로, 물체의 이익과 무게가 주어집니다. 그리고 W 는 배낭 용량 입니다.
이제 1 단계에서 임의의 요소를 선택하는 대신 중앙값 찾기 알고리즘 을 적용 할 수 있습니다. 중앙값을 O (n) 번 찾습니다.
그러면 나머지 모든 단계를 수행 할 수 있습니다.따라서 시간 복잡도 분석은-
        T (n) = T (n / 2) + O (n).
그리고 우리는 해결책으로 O (n) 를 얻을 것입니다. 제대로 설명되지 않은 것이 있고 더 알고 싶은 것이 있으면 알려주세요.

선형 시간에서 다음을 찾을 수 있습니다. 단위 중량 당 가치 측면에서 중앙값. 그런 다음 선형 시간에서도 배낭에 최소한 그만한 가치가있는 모든 항목을 넣을 수 있는지 여부를 파악할 수 있습니다. 할 수 있다면 그렇게하여 n / 2 항목에 대해이 문제를 재귀 적으로 해결하십시오. ” 냅색을 이미 채웠습니다. 할 수 없다면 값이 낮은 n / 2 항목을 버릴 수 있습니다. 그런 다음 가장 높은 가치의 n / 2 항목 만 사용하여 문제를 다시 해결해보십시오.

여기에서 반복은 T (n) = T (n / 2) + O (n) 입니다. 원하는대로 div id = “813b46dcfa”>