0

このアルゴリズムをどのように設計するのが最善かについて混乱しています。船には x 人の海賊がいて、j番目の海賊の年齢は a jで、j番目の海賊の体重は w jです。私は、すべての海賊の 25 パーセンタイルから 75 パーセンタイルの重みを持つ最年長の海賊を見つける動的計画法アルゴリズムを考えています。しかし、私はどのように進めるかについて無知です。

4

4 に答える 4

3

素朴な解決策（おそらく最も効率的ではありませんが、頭に浮かんだ最初の解決策であり、素晴らしくシンプルです）：

海賊のリストを重みで並べ替えます。次に、リストの中央の 50% をループして、年齢が最大の海賊を探します。

効率的なソート アルゴリズムを使用すると仮定すると、実行時間は n log(n) + n/2 -> O(n log(n)) になります。

于 2010-04-22T16:00:38.340 に答える
2

可能な O(n) ソリューションがあります。

必要な条件は、重みが整数として扱われ、何らかの上限によって拘束される必要があることです。現実の世界では、誰かの体重を表すときに小数点以下 1 桁しか必要としないため、これは真実です。そして、あなたは10000ポンド以上の重さを言うことはできません.

次に、バケット ソート(O(n)) を使用して、興味深いパーセンタイルの制限がどこにあるかを調べ、そこにある最も古い海賊 (これも O(n)) を単純に探すことができます。

編集、明確化：

重み自体は整数であってはなりませんが、精度が (固定された適切な小数点以下の桁数に) 制限されている限り、整数になるように常にそれらすべてを掛けることができます。たとえば、1678 として 167.8 の重みを表します。

編集、バケットの並べ替えの説明:

詳細な説明が必要な場合は、ウィキペディアの記事をお読みください。ここでは、あなたのケースの例を作成します。というリストがあるとしpiratesます。次に、それらを新しいリストに並べ替えることができますsortedPirates。そして、前に説明したように、これが機能するための要件は、1) 海賊の重みが整数である (またはそのように表現できる) こと、および 2) 個別の重みの数 (または重みの表現) が上限に拘束されていることです。ここでは、整数の重みと 10000 ポンドの上限を想定しています。

// Put the pirates into buckets (each bucket is a linked list, or null if empty)
var upperWeightBound = 10000;
var buckets = new LinkedList<Pirate>[upperWeightBound];
foreach (var pirate in pirates)
{
    if (buckets[pirate.weight] == null)
        buckets[pirate.weight] = new LinkedList<Pirate>();
    buckets[pirate.weight].AddLast(pirate);
}

// Extract the bucketed pirates into a single, now sorted, linked list
var sortedPirates = new LinkedList<Pirate>();
foreach (var bucket in buckets)
    if (bucket != null)
        foreach (var pirate in bucket)
            sortedPirates.AddLast(pirate);
于 2010-04-22T16:33:17.307 に答える
1

頭のてっぺんから、データを重量でソートし、j = 1/4 * x で海賊として最小重量を選択し、j = 3/4 * x で海賊として最大許容重量を選択します。次に、一連の海賊の体重が最小値より大きいか最大値より大きいかを確認します。このチェックが成功した場合、この海賊は候補になる可能性があります。現在の候補者がいない場合は、この海賊を現在の候補者として選択します。現在の候補者がいる場合、年齢が現在の候補者よりも大きい場合にのみ、この海賊を新しい現在の候補者として選択します。

候補のソートは O(nlogn) で実行できます。適切なデータ構造を使用して上限/下限の重みを選択することは、O(1) 操作です。最も古い適格な候補を見つけることは O(n) です。したがって、アルゴリズム全体は O(nlogn) です。

C# 用のスニペット コンパイラの使用:

public class Pirate
{
    public int ID { get; set; }
    public int Age { get; set; }
    public int Weight { get; set; }
}


var pirates = new List<Pirate>();
int max = 20;

Random rng = new Random();
for (int j = 0; j < max; ++j)
{
    var pirate = new Pirate();
    pirate.ID = j;
    pirate.Age = rng.Next(45) + 15;
    pirate.Weight = rng.Next(100) + 100;
    pirates.Add(pirate);
}

pirates.Sort( (a,b) => a.Weight.CompareTo( b.Weight ) );

int lowWeight = pirates[max/4].Weight;
int highWeight = pirates[max*3/4].Weight;

Pirate chosen = null;
foreach (var pirate in pirates)
{
    if (pirate.Weight >= lowWeight && pirate.Weight <= highWeight)
    {
        if (chosen == null || pirate.Age > chosen.Age)
        {
            chosen = pirate;
        }
    }
}

Console.WriteLine( "Chosen {0}: Age {1}, Height {2}", chosen.ID, chosen.Age, chosen.Weight );
于 2010-04-22T16:06:00.553 に答える
1

線形時間でかなり効率的に解決できます。

1) 線形時間 i 次統計「選択アルゴリズム」を使用して、体重が 25 パーセンタイルの海賊を見つけます。

2) 再び同じアルゴリズムを使用して、体重が 75 パーセンタイルの海賊を見つけます。

3) これら 2 つの境界内にある海賊をフィルターで除外します。これも線形時間です。

4) 適格な海賊について、年齢基準で MAX を計算します。-- 再び線形時間で。

于 2011-03-06T05:07:08.663 に答える