Dynamic Programming Algorithm?

Question

I am confused about how best to design this algorithm. A ship has x pirates, where the age of the j^th pirate is a_j and the weight of the j^th pirate is w_j. I am thinking of a dynamic programming algorithm, which will find the oldest pirate whose weight is in between twenty-fifth and seventy-fifth percentile of all pirates. But I am clueless as to how to proceed.

Answer 1

Naive solution (probably not the most efficient but the first one that pops into my head, and is nice and simple):

Sort the list of pirates by weight. Then loop over the middle 50% of the list searching for the pirate with the maximum age.

Assuming you use an efficient sorting algorithm the runtime would be n*log(n) + n/2 -> O(n*log(n)).

Answer 2

Of the top of my head, I'd sort the data by weight, then choose minimum weight as the pirate at j = 1/4 * x and the maximum allowable weight as the pirate at j = 3/4 * x. Then I'd iterate through the set of pirates checking if their weight is greater than the minimum or greater than the maximum. If this check succeeds, then this pirate may be a candidate. If there is no current candidate, then select this pirate as the current candidate. If there is a current candidate, then select this pirate as the new current candidate only if his age is greater than the current candidate.

Sorting the candidates can be done in O(nlogn). Selecting the upper/lower weight, with a suitable data structure, is an O(1) operation. Finding the oldest qualifing candidate is O(n). So the total algorithm is O(nlogn).

Using Snippet Compiler for 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 );

Answer 3

There is a possible O(n) solution.

The required condition is that weights must be treated as integral and bound by some upper limit. In the real world, this is true since we never really need more than one digit after the decimal point when describing someones weight. And you cant weigh more than say 10000 pounds.

Then you can use bucket sort (which is O(n)) to find out where the limits for the interesting percentile is and then simply look for the oldest pirate in there (which is also O(n)).

Edit, clarification:

The weights themselves must not be integral, but as long as the precision is limited (to a fixed and reasonable number of decimals) you can always multiply them all so that they become integral. For example, represent a weight of 167.8 as 1678.

Edit, explaining bucket sort:

Read the wikipedia article if you want a detailed description. I'll just make an example for your case here. Assume that there is a list called pirates. Then we can sort them into a new list sortedPirates. And as I explained before, a requirement for this to work is that 1) the pirate weights are integral (or can be represented as such) and 2) the number of distinct weights (or representation of weights) are bound by an upper limit. I've assumed integral weights and an upper bound of 10000 pounds here:

// 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);