C# aggregation function for a non-linear series

Question

I'm given two arrays, one representing a price, the other representing a number of units:

e.g.

decimal[] price = new decimal[] {1.65, 1.6, 1.55, 1.4, 1.3};
long[] quantity = new long[] {5000, 10000, 12000, 20000, 50000};

So the first 5000 units will cost 1.65 each, the next will cost 10000 will cost 1.6 each, and so on...

It's pretty easy to get the average price with an aggregate funct when you know the amount of units you wish to order e.g.Average price for 7000 units = (5000/7000 * 1.65) + (2000/7000 * 1.6), however, I'm having trouble coming up with an algorithm for when the total unit amount is the unknown variable, and we are given the target average price.

E.g. How many units would I have to order so the average unit price = 1.57

Answer 1

If you think geometrically about it, consider a chart showing the total price (ordinate axis) as a function of the total number of items (abscissa) bought. The plot starts in (0, 0) (buying zero costs zero). First we get a straight line segment of slope 1.65 and horizontal width 5000. Then from the end-point of that comes a new segment of slope 1.6 and width 10000. The total plot is continuous and piece-wise straight-lined but with bends where the unit price changes.

Then to solve your problem, find the intersection with the line of equation y == 1.57 * x, i.e. the line starting at (0, 0) and having slope 1.57. For each of the segments (whose two endpoints you know), check if this segment meets y == 1.57 * x, and if it does, there's your solution.

If the numbers in your price array are decreasing, there can be at most one solution (given that 1.57 is strictly less than the first price, price[0]), the plot representing a concave function.

EDIT: I tried to code this geometry in C#. I didn't add checks that price are all positive and decreasing, and that quantity are all positive. You must check that. Here's my code:

        decimal[] price = { 1.65m, 1.6m, 1.55m, 1.4m, 1.3m, };
        long[] quantity = { 5000, 10000, 12000, 20000, 50000, };
        decimal desiredAverage = 1.57m;

        int length = price.Length;
        if (length != quantity.Length)
            throw new InvalidOperationException();

        var abscissaValues = new long[length + 1];
        var ordinateValues = new decimal[length + 1];
        for (int i = 1; i <= length; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                abscissaValues[i] += quantity[j];
                ordinateValues[i] += price[j] * quantity[j];
            }
        } // calculation of plot complete

        int segmentNumber = Enumerable.Range(1, length).FirstOrDefault(i => ordinateValues[i] / abscissaValues[i] <= desiredAverage);
        if (segmentNumber > 1)
        {
            decimal x = (ordinateValues[segmentNumber - 1] * abscissaValues[segmentNumber] - abscissaValues[segmentNumber - 1] * ordinateValues[segmentNumber])
                / (desiredAverage * (abscissaValues[segmentNumber] - abscissaValues[segmentNumber - 1]) - (ordinateValues[segmentNumber] - ordinateValues[segmentNumber - 1]));
            Console.WriteLine("Found solution x == " + x);
        }
        else
        {
            Console.WriteLine("No solution");
        }

I don't know if someone can write it more beautifully, but it seems to work. Output is:

Found solution x == 29705.882352941176470588235294

Answer 2

I believe that's because there's no one answer, no one combination of prices which will result in one average, no close form equation. What we may be looking at is a variant of the Knapsack Problem. http://en.wikipedia.org/wiki/Knapsack_problem with a minimization of value instead of maximization.

EDIT: As correctly pointed out below, this is not a variant of the knapsack problem. There is a closed form solution:

If T = total units bought,

1.57 = 1.55 * (12000/T) + 1.6 * ((T-12000)/T). Solve for T.

The starting price block (here 1.55) is the block just below the average price per unit given in the problem (here 1.57).