다음 (비현실적인!) 투자 문제를 고려하십시오

Question

다음과 같은 (비현실적인!) 투자 문제를 고려하십시오.

우리는 잠재적 투자의 집합 S를 가지고 있습니다. 각 투자는 부동 소수점 수 (금액, 추정 수익률)로 주어집니다. 투자 할 총 금액이 있습니다. 우리는이 금액에 대한 수익을 극대화하기 위해 투자를 선택하려고합니다.

전체 투자 (a, r 모두 소비)를 선택하거나 f (지출 (f * a) 만 선택하고 f * r) return). 선택 세트의 예상 수익은 개별 선택의 수익 합계입니다. 분명히, S의 요소를 선택할 때, 우리는 사용할 수있는 총량 A 이상을 쓸 수 없습니다.

금액 A 및 투자 금액 S로 실현할 수있는 최대 예상 수익 계산을위한 효율적인 알고리즘을 설명하십시오. 알고리즘의 시간 복잡도는 얼마입니까?

최상의가요?

알고리즘을 단어 및/또는 의사 코드로 설명하는 것이 좋습니다. 프로그래밍 언어로 코드를 포함 할 필요가 없습니다.

Answer 1

이것은 fractional knapsack problem입니다. 이것은 정수형 카운터와는 달리, 탐욕스러운 알고리즘으로 최적의 솔루션을 찾기 위해 운 좋게 쉽게 해결할 수 있습니다. 감소 비율 (r)에 따라 투자를 주문하여

1. 시작/A는
2. 는 순서대로 투자 가능한 자금을 할당합니다. 나는. 모든 첫 번째 투자를 구매 한 다음 사용 가능한 돈을 사용하여 두 번째 투자를 구매 한 다음 세 번째 등을 구매하여 돈을 완납 할 때까지

복잡도는 비율을 계산하기 위해 O (n), 투자를 정렬하기 위해 O (n logn), 돈을 할당하기 위해 O (n)을가집니다. 이것은 전체 알고리즘이 O (n logn)임을 의미합니다.