Массив процентов, который может содержать до 100

Question

В интервью мне задали следующий вопрос, и я все еще думаю об эффективном способе его выполнения.

У вас есть массив, числа которого представляют процентные доли жидкостей в стволе. У вас также есть API с методом: combine(int x,int y), который принимает два входных процента в массиве и объединяет жидкость из одного ствола в другой. Используя эту информацию, вы должны найти максимальное количество бочек, которые могут быть доступны при 100% -ной жидкости.

Пример 1. Массив: 10,15,20,35,55,65

Ans: Количество баррелей будет 2. Так как combine(65,35) --- один 100% баррель, combine(55,20) --75% бочка, рядом combine(75,15) --90% в следующем combine(90,10) --100% - 1 баррель Так всего 2 бочки

Пример 2: 99,99,99

Ans: Количество бочек было бы 1 здесь, так как вы делаете combine(99,99) - вы получаете один 100% бочонок, остальная часть жидкости теряется впустую, и вы не можете комбинировать другие бочки с третьим 99% стволом, чтобы сделать it 100

Примечание: после того, как вы выливаете жидкость из одной бочки в другую, вы не сможете использовать ее снова для: combine(55,15) - 70% ствола. Вы можете использовать 70% барреля, но не 55% и 15% баррелей.

Answer 1

Возможно, вы действительно посмотрите на алгоритмы для проблемы упаковки корзины. This student paper указывает четыре из них. Тот, у кого наилучшее приближение, - это сокращение первого Fit algo.

Это сводится к быстрому сортировке (на месте, O (nlogn) временная сложность в среднем и O (n2) в худшем случае), а затем First Fit.

First Fit подходит для сканирования бункеров по порядку и поместите новый элемент в первый бункер, который достаточно велик, чтобы его удерживать. Если в нем нет вставки, в который установлен текущий объект, запустите новый ящик.

Для определения сложности FF в O (nlogn) используйте структуру данных дерева Winner Max. Он имеет n внешних узлов (игроков) и n-1 внутренних узлов (победитель для каждого матча), , а победителем является игрок с максимальным значением.

Answer 2

Предполагая, что все проценты в заданном массиве меньше 100 (в любом случае, если бы были элементы размером более 100, мы могли бы сразу их отсчитать и удалить), каждый баррель 100% не может быть создан из менее чем двух элементы массива, а число 100% баррелей не может быть больше, чем сумма массива, деленное на 100. Таким образом, возможности для изучения связаны:

maxNumBarrels array = min (div (sum array) 100) (div (length array) 2) 

Следующий код Haskell обеспечивает функцию, divide, который разбивает массив на все варианты n разделов без повторения (т. е. игнорируются и порядок разделов, и порядок элементов в разделах). Функция, maxBarrels, выполняет поиск назад, деля массив сначала на разделы maxNumBarrels (поиск результатов с элементами maxNumBarrels, сумма которых равна> = 100), а затем постепенно уменьшаются числа разделов до тех пор, пока не будет найден ответ или не будет установлен нулевой набор.

import Data.Map (adjust, fromList, toList) 

divide xs n = divide' xs (zip [0..] (replicate n [])) where 
    divide' []  result = [result] 
    divide' (x:xs) result = do 
    index <- indexes 
    divide' xs (toList $ adjust (x :) index (fromList result)) where 
     populated = map fst . filter (not . null . snd) $ result 
     indexes = populated ++ if any (null . snd) result 
           then [length populated] 
           else [] 

maxBarrels xs = allDivided maxNumBarrels where 
    maxNumBarrels = min (div (sum xs) 100) (div (length xs) 2) 
    allDivided count | count == 0   = [] 
        | not (null divided) = divided 
        | otherwise   = allDivided (count - 1) 
    where divided = filter ((==count) . length) 
        . map (filter ((>=100) . sum)) 
        . map (map snd) 
        . divide xs $ count 

ВЫВОД:

*Main> maxBarrels [10,15,20,35,55,65] 
[[[55,20,15,10],[65,35]],[[55,35,10],[65,20,15]]] 

*Main> maxBarrels [99,99,99] 
[[[99,99,99]]] 

*Main> maxBarrels [99,99,99,10,15,25,35,55,65] 
[[[15,10,99],[25,99],[35,99],[65,55]] ...(the first of 144 immediate results)...