0

我对如何最好地设计这个算法感到困惑。一艘船有 x 个海盗，其中第 j个海盗的年龄为 a j ，第 j个海盗的体重为 w j。我正在考虑一种动态规划算法，它将找到体重在所有海盗的百分之二十五到七十五之间的最年长的海盗。但我不知道如何进行。

4

4 回答 4

3

天真的解决方案（可能不是最有效的，但第一个突然出现在我脑海中的解决方案，又好又简单）：

按重量对海盗列表进行排序。然后遍历列表的中间 50%，搜索年龄最大的海盗。

假设您使用有效的排序算法，运行时间将为 n log(n) + n/2 -> O(n log(n))。

于 2010-04-22T16:00:38.340 回答
2

有一个可能的 O(n) 解决方案。

要求的条件是权重必须被视为整数并受某个上限的约束。在现实世界中，这是真的，因为在描述某人的体重时，我们从来不需要小数点后一位以上的数字。而且你的体重不能超过 10000 磅。

然后，您可以使用桶排序（即 O(n)）找出有趣百分位数的限制在哪里，然后简单地寻找其中最古老的海盗（这也是 O(n)）。

编辑，澄清：

权重本身不能是整数，但只要精度有限（限制为固定且合理的小数位数），您始终可以将它们全部相乘，使它们成为整数。例如，将 167.8 的权重表示为 1678。

编辑，解释桶排序：

如果您需要详细说明，请阅读维基百科文章。我将在这里为您的案例举一个例子。假设有一个名为 的列表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

您可以在线性时间内非常有效地解决它。

1) 使用线性时间 i 阶统计“选择算法”找到权重为第 25 个百分位的海盗。

2) 再次使用相同的算法找到体重为 75% 的海盗。

3）过滤掉落在这两个范围内的海盗——再次在线性时间。

4) 对于合格的海盗，根据年龄标准计算 MAX。- 再次在线性时间。

于 2011-03-06T05:07:08.663 回答
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 回答