UniLecs #124_1. Диверсификация
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
Реализация:
- @akolosov364, JS: 1 балл
Перебор всех возможных вариантов с выбором лучшего из них. Функция share расскидывает все возможные варианты, когда нечего расскидывать сравнивает с эталонным значением.
https://gist.github.com/KolosovAO/dfd02b078ee18f7ce00d67c56b1c15ac
Test:
https://repl.it/@unilecs/task124
2. @jinxonik, Python: 1.6 балла за два подхода на Python/C++
Генерируем все возможные варианты и используем для одного из списков тот, что наиболее близок к половине суммы исходного списка. Второй список генерируем исключением элементов первого из исходного.
https://gist.github.com/jin-x/d0b9b250f5225614c039590daf36aeac
Test:
https://repl.it/@jin_x/UniLecs-124-TwoListspy
C++
https://gist.github.com/jin-x/8a90dc5e83b3eb68c21fd57541ad815b
Test C++:
https://repl.it/@jin_x/UniLecs-124-TwoListscpp
3. @tvolf, PHP: 1 балл
Классическая задача о разбиении массива на две группы элементов таким образом, чтобы разность сумм их элементов была минимальной. Для поиска лучшего решения будем рассматривать все возможные выборки элементов из заданного массива размерностью N. Для этого рассмотрим двоичные представления чисел от 0 до 2^N-1. Единичный бит в числе будет означать, что данный элемент выбран.
https://gist.github.com/tvolf/0662be8e91e65a16610028259ddbc628
4. Антон, Rust: 1 балл
https://gist.github.com/AnthonyMikh/be3193d89496e8cdfc075d6ed0fa6886
Test:
https://play.rust-lang.org/?gist=9dd2ac2ab65c129d5bef51cfc57ec7d7
5. @lPestl, C#: 1 балл
https://gist.github.com/lpestl/01887ae8327d2dac3dd77fbe3dde9554
6. @LostInKadath, C++: 1 балл
https://gist.github.com/LostInKadath/2ca0fb9aa5f6c51e812a6fdd4e23626a
7. @Zernov_A, Java: 1 балл
Перебор всех возможных комбинаций ценных бумаг и нахождение той комбинации, при которой разница в стоимости этих портфелей была минимальной. Для ускорения процесса, если нашли комбинацию, при которой разница в стоимости = 0, то дальнейший поиск прекращаем. Комбинации находим путем перебора чисел от 0 до 2^n. Каждое такое число представляем в двоичном виде (010011..), кол-во цифр = кол-ву ценных бумаг. Если на i-м месте стоит "1", то ценная бумага Аi попадает в первый портфель, если "0" - то во второй.
https://github.com/AlexZDeveloper/InvestmentPortfolio
8. @lalabuy, Haskell: 1 балл
https://gist.github.com/lalabuy948/ab6a64d8951ed2eb9f689ccb58333092
Test:
https://repl.it/repls/telegram124
9. @egormasharskii, С++: 1.5 балла
Метод 1. Генерируем все маски длины n бит и для каждой маски (разбиения) считаем ее цену. Сложность O(n*2^n) Цена второго разбиения получается овтоматически. Дальше сравниваем разность разбиения и выбираем лучшее
Метод 2. Рекурсивно генерируем все подмножества и выбираем наилучшее разбиение. Сложность - очевидно O(2^n). По сравнению с предыдущим вариантом не надо бегать по маскам для вычисления цены разбиения.
https://gist.github.com/myegor/9aebd754439250b9987ed015befc7576
Test: