UniLecs #124. Диверсификация

UniLecs #124. Диверсификация

UniLecs
Кризис в 1998, 2008, 2014. 2018 ?! Будьте аккуратны!

Задача: у вас есть портфель ценных бумаг: A1, A2, A3,..., An. Необходимо диверсифицировать его на два отдельных портфеля, но так, чтобы разница в стоимости этих портфелей была минимальной.

Входные данные: Shares[] - массив ценых бумаг, где Shares[i] - цена i-й акции. Размер массива от 1 до 20, цена любой акции от 1 до 10^3.

Вывод: FirstShares[], SecondShares[] - массивы с ценами бумаг для 1го и 2го портфеля соот-но, а также стоимость каждого из портфелей.

Пример: Shares = [1, 2, 3, 3]

Answer: 

FirstShares = [1, 3], FirstTotalValue = 4; 

SecondShares = [2, 3], SecondTotalValue = 5

Идея: по сути эта одна из вариаций задачи о рюкзаке. Нам нужно перебрать все возможные расположения ценных бумаг в портфелях. 

Для этой задачи воспользуемся битовой маской (ее размер равен кол-ву ценных бумаг). На каждом шаге перебора смотрим все биты числа, и если i-й бит равен единице, то i-й элемент будет входить в комбинацию.

Например, i-й бит равен 1, тогда i-я ценная бумага находится в 1м портфеле; если 0 - то во втором портфеле. Всего будет (2^N - 1) различных расположений, где N - кол-во ценных бумаг в исходном портфеле.

Разберем на нашем примере:N = 4; Shares = [1, 2, 3, 3];

NumberOfPairs = 2^4 = 16:

  1. 1 в двоичной системе = 0001 -> [1, 0, 0, 0] (т.е. берем в 1й портфель 1ю ценную бумагу, остальные пойдут во 2й портфель)
  2. 2 в двоичной системе = 0010 -> [0, 2, 0, 0] (т.е. берем в 1й портфель 2ю ценную бумагу, остальные пойдут во 2й портфель)
  3. 3 в двоичной системе = 011 -> [1, 2, 0, 0] (т.е. берем в 1й портфель 1ю и 2ю ценную бумагу, остальные пойдут во 2й портфель)

...

13. 13 в двоичной системе = 1101 -> [1, 0, 3, 3] (т.е. берем в 1й портфель 1ю, 3ю и 4ю ценную бумагу, остальные пойдут во 2й портфель)

14. 14 в двоичной системе = 1110 -> [0, 2, 3, 3] (т.е. берем в 1й портфель 2ю, 3ю и 4ю ценную бумагу, остальные пойдут во 2й портфель)

15. 15 в двоичной системе = 1111 -> [1, 2, 3, 3] (т.е. все ценные бумаги пойдут в 1й портфель, второй портфель пустой)

Для каждого из расположений мы считаем сумму ценности бумаг и среди всех расположений ищем такую, при ктр разница стоимости портфелей будет наименьшей. 

Реализация:

C#: GetPortfolioValue() func
C#: Diversification() func
C#: Main() func

https://gist.github.com/unilecs/14cfa9c8e236da8bece84eda76c20963

Test:

https://dotnetfiddle.net/Jdebsd

Report Page