Учитывая большой список предметов с ценой и стоимостью, выберите самую дешевую комбинацию из 10 предметов со средним значением, большим или равным фиксированному значению

Question

Я не специалист по информатике, поэтому у меня довольно ограниченное знание алгоритмы. В последнее время я думал о каком-то рыночном боте, и у меня есть ключевой вопрос, с которым я не могу справиться с грубой силой.

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. 

Я думал, что из нескольких алгоритмов, такие как:

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

Очевидно, что это не даст истинное дешевое сочетания, но, надеюсь, достаточно близко? Я ценю любую помощь.

Answer 1

Вы можете решить эту проблему с помощью целочисленного линейного программирования. Пусть значение элемента i будет v [i] и его стоимость c [i]. Пусть x [i] - количество каждого купленного вами товара (который может принимать значения 0 или 1), а V - минимально приемлемое общее значение. Ограничение 0/1 на x [i] делает это целочисленной линейной программой, а не простой линейной программой.

Тогда вы хотите минимизировать сумму (c [i] * x [i]) такую, что сумма (v [i] * x [i])> = V и сумма (x [i]) = 10, что является проблемой правильной формы, которая должна быть решена как ИЛП.

Вот хороший открытый исходный код решатель: https://www.gnu.org/software/glpk/