UniLecs #124. Диверсификация
UniLecs
Задача: у вас есть портфель ценных бумаг: 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 в двоичной системе = 0001 -> [1, 0, 0, 0] (т.е. берем в 1й портфель 1ю ценную бумагу, остальные пойдут во 2й портфель)
- 2 в двоичной системе = 0010 -> [0, 2, 0, 0] (т.е. берем в 1й портфель 2ю ценную бумагу, остальные пойдут во 2й портфель)
- 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й портфель, второй портфель пустой)
Для каждого из расположений мы считаем сумму ценности бумаг и среди всех расположений ищем такую, при ктр разница стоимости портфелей будет наименьшей.
Реализация:



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