CODEWITHSUNDEEP
algorithmcombinatorics
nuno
nuno

Reputation: 53

Algorithm to pick elements of collection to achieve average price

I need to solve the following problem:

I have an array of items with a price attached and I need to pick a given quantity to achieve a given weighted average price.

eg.

I can group quantities in bins for the same price for better understanding:

price    qty
$1.00    60
$1.04    80
$0.99    55
$1.10    130

Now I need to choose how many elements I need from each bin to achieve 100 elements at an average price = 1.035

Do you know an algorithm to search for an approximate solution without brute force combination? - I am time constrained too.

It looks some sort of the knapsack algorithm, although I'm not sure of the restrains I must use.

Thank you

Upvotes: 1

Views: 57

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58221

This is an integer linear programming problem.

Expressing this as a linear programming problem would mean having variables a, b, c, d with a+b+c+d=100, and a*1+b*1.04+c*0.99+d*1.10=1.035*100 and 0<=a<=60, 0<=b<=80, 0<=c<=55 and 0<=d<=130.

You don't explicitly say, but probably want integer solutions (that is, the quantities bought must be integers), hence it's an integer linear programming problem, rather than a linear programming problem. Although ILP problems are NP-hard in general, you can find solvers and algorithms online that will easily solve this small problem. For example, try GLPK.

Note also, that brute force will work well here; there's only 176851 combinations of a,b,c,d to try.

Upvotes: 2

Related Questions