CODEWITHSUNDEEP
algorithmmathlanguage-agnosticcombinations
jazzcool
jazzcool

Reputation: 183

Given a big list of items with a price and a value, choose the cheapest combination of 10 items with an average value greater or equal to a fixed val

I'm not a computer science major, so I have fairly limited knowledge of algorithms. Lately I was thinking of a market bot of some sort and I have a key question that I cannot handle with brute-force.

Question: Let there be a list of items, where number of items are greater
than 10000. Each item has a value in between 0 and 1, and a price. Value and
price are independent of each other. You must choose the cheapest 10 items
where their average (or total) value is greater or equal than a given value.

I thought of several algorithms such as:

-Sort the list by price
-Divide the list in 5 item chunks, reducing the brute
force steps from 10000nCr10 to 2000nCr2.

Obviously it will not give the true cheapest combination, but hopefully close enough? I appreciate any help.

Upvotes: 0

Views: 316

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58221

You can solve it using integer linear programming. Let the value of item i be v[i] and its cost c[i]. Let x[i] be the number of each item you buy (which can take the values 0 or 1), and V be the minimum acceptable total value. The 0/1 constraint on x[i] makes this an integer linear program rather than a simpler linear program.

Then you want so minimize sum(c[i]*x[i]) such that sum(v[i]*x[i]) >= V and sum(x[i]) = 10, which is a problem of the right form to be solved as an ILP.

Here's a good open-source solver: https://www.gnu.org/software/glpk/

Upvotes: 1

Related Questions