3

我在一次采访中被问到以下问题，我仍在考虑一种有效的方法。

您有一个数组，其数字表示桶中液体的百分比。您还有一个带有方法的 API：combine(int x,int y)它接受数组中的两个输入百分比并将液体从一个桶合并到另一个桶。通过使用此信息，您必须找到 100% 液体可能的最大桶数。

示例 1.数组：10,15,20,35,55,65

Ans : 桶数为 2。因为combine(65,35)---一个 100% 桶，-- combine(55,20)75% 桶，下一个 --90%combine(75,15)下一个combine(90,10)--100%--1 桶 所以总共 2 桶

示例 2：99,99,99

回答：因为你这样做，所以这里的桶数将是 1——combine(99,99)你得到一个 100% 的桶，其余的液体被浪费了，你不能将任何其他桶与第三个 99% 的桶结合起来使其成为 100

注意：一旦您将液体从一个桶倒入另一个桶，您就不能再次使用它，例如：-- combine(55,15)70% 桶。您可以使用 70% 的桶，但不能使用 55% 和 15% 的桶。

4

2 回答 2

2

您可能确实会查看装箱问题的算法。这篇学生论文指出了其中的四个。具有最佳近似值的是递减第一次拟合算法。

它归结为快速排序（就地，平均时间复杂度为 O(nlogn)，最坏情况下为 O(n2)），然后是 First Fit。

First Fit 下来按顺序扫描箱子，然后将新物品放入第一个足够大的箱子中以容纳它。如果没有适合当前对象的 bin，则启动一个新 bin。

对于 O(nlogn) 复杂度的 FF，使用 Max Winner Tree 数据结构。它有n个外部节点（玩家）和n-1个内部节点（每场比赛的获胜者），获胜者是具有最大值的玩家。

于 2013-04-28T17:09:11.367 回答
1

假设给定数组中的所有百分比都小于 100（在任何情况下，如果有元素等于或大于 100，我们可以立即计数并删除它们），每桶 100% 不能由少于两个数组元素创建，并且100% 桶的数量不能超过数组的总和除以 100。因此，检查的可能性受以下限制：

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

下面的 Haskell 代码提供了函数 ，divide它将数组划分为 n 个分区的所有变体而不重复（即，分区中的分区顺序和元素顺序都被忽略）。函数 ,maxBarrels向后搜索，首先将数组划分为 maxNumBarrels 分区（搜索总和 >=100 的 maxNumBarrels 元素的结果），然后逐渐减少分区数量，直到找到答案或返回空集。

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)...
于 2013-04-29T01:20:33.717 回答