百分比數組可以加起來最多爲100

我在採訪中被問及以下問題，並且我仍在考慮一種有效的方法。百分比數組可以加起來最多爲100

您有一個數組，其數字代表桶中液體的百分比。您還有一個方法的API：combine(int x,int y)，它在陣列中需要兩個輸入百分比，並將液體從一個桶移到另一個桶。通過使用這些信息，您必須找到100％液體可能的最大數量的桶。

實施例1陣列：10,15,20,35,55,65

答：桶數量將是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％的桶組合它100

注意：一旦你從一個桶倒液到另一個你不能再次使用它例如：combine(55,15) - 70％桶。您可以使用70％的桶，但不能使用55％和15％的桶。

來源

2013-04-27 chitu fds

這似乎是裝箱的變化，這是NP難，但有很多很好的近似方案。你需要找到最佳答案還是可以近似它？ – Paulpro 2013-04-27 20:46:57

Paulpro提到的用於裝箱的鏈接http://en.wikipedia.org/wiki/Bin_packing_problem。它的推薦閱讀讓你瞭解和選擇你選擇的方法來解決問題。 – Zeddy 2013-04-27 23:32:51

@Paulpro變體？這看起來像一個確切的BPP給我。 – 2013-04-28 17:15:11

你確實可以看看bin裝箱問題的算法。 This student paper表示其中四個。具有最佳逼近的那個是降低首次擬合算法。它歸結爲快速排序（就地，平均O（nlogn）時間複雜度和最差情況下O（n2）），然後是第一次適應。

首次檢查可以按順序掃描箱子，並將新物品放置在足夠大的第一個箱子中。如果當前對象沒有適合的倉位，請啓動一個新倉位。

對於O（nlogn）複雜度的FF，使用Max Winner Tree數據結構。它有n個外部節點（玩家）和n-1個內部節點（每場比賽獲勝者），，獲勝者是最大值的玩家。

來源

2013-04-28 17:09:11 octoback

假設所有的百分比給定的陣列中是小於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

OUTPUT：

*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-29 01:20:33

百分比數組可以加起來最多爲100

回答

相關問題