3

インタビューで次の質問をされましたが、効率的な方法をまだ考えています。

数字がバレル内の液体のパーセンテージを表す配列があります。メソッドを持つ API もあります。combine(int x,int y)これは、配列内の 2 つの入力パーセンテージを取り、あるバレルから別のバレルへの液体を結合します。この情報を使用して、100% 液体で可能なバレルの最大数を見つける必要があります。

例 1.配列: 10,15,20,35,55,65

回答:バレル数は 2 になりますcombine(65,35)。100% バレルが 1 つ、 combine(55,20)-75% バレルが 1 つ、次が --90 combine(75,15)% 次combine(90,10)が --100%--1 バレル 合計 2 バレルです。

例 2: 99、99、99

回答:ここでは樽の数は 1 になります。combine(99,99)つまり、100% の樽が 1 つ得られ、残りの液体は無駄になり、他の樽を 3 つ目の 99% の樽と組み合わせて 100 にすることはできません。

注: あるバレルから別のバレルに液体を注ぐと、それを再び使用することはできません。例: combine(55,15)--70% バレル。70% バレルは使用できますが、55% および 15% バレルは使用できません。

4

2 に答える 2

2

実際、ビンパッキング問題のアルゴリズムを見ることができます。この学生論文はそのうちの4つを示しています。最良の近似値は、最初の適合アルゴリズムの減少です。

それは、クイックソート（その場で、平均でO（nlogn）時間の複雑さ、最悪の場合O（n2））、そしてFirst Fitになります。

First Fit が降りてきてビンを順番にスキャンし、新しいアイテムをそれを保持するのに十分な大きさの最初のビンに入れます。現在のオブジェクトが収まるビンがない場合は、新しいビンを開始します。

O(nlogn) の複雑さで FF するには、Max Winner Tree データ構造を使用します。n 個の外部ノード (プレーヤー) と n-1 個の内部ノード (各試合の勝者) があり、勝者は最大値を持つプレーヤーです。

于 2013-04-28T17:09:11.367 に答える
1

指定された配列内のすべてのパーセンテージが 100 未満であると仮定すると (いずれにせよ、100 以上の要素があった場合は、すぐに数えて削除することができます)、100% の各バレルは 2 つ未満の配列要素から作成することはできません。 100% バレルの数は、配列の合計を 100 で割った値を超えることはできません。したがって、調べる可能性は次のように制限されます。

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

次の Haskell コードは関数 を提供します。この関数はdivide、配列を繰り返しなしで n 個のパーティションのすべてのバリエーションに分割します (つまり、パーティション内のパーティション順序と要素順序の両方が無視されます)。関数maxBarrelsは逆方向に検索し、最初に配列を maxNumBarrels パーティションに分割し (合計が >=100 である maxNumBarrels 要素を含む結果を検索します)、答えが見つかるか null セットが返されるまで、パーティションの数を徐々に減らします。

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 に答える