Алгоритм выбора элементов коллекции для достижения средней цены

Question

Мне нужно решить следующую проблему:

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

например ,

Я могу группировать количества в бункерах по одной цене для лучшего понимания:

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

Теперь мне нужно выбрать, сколько элементов мне нужно из каждого бина, чтобы получить 100 элементов по средней цене = 1.035

Знаете ли вы алгоритм для поиска приближенного решения без комбинации грубой силы? - Я тоже ограничен во времени.

Это похоже на алгоритм ранца, хотя я не уверен, какие ограничения я должен использовать.

Спасибо

Answer 1

Это целочисленная задача линейного программирования.

Выражение этой задачи как задачи линейного программирования означало бы наличие переменных a, b, c, d с a+b+c+d=100 и a*1+b*1.04+c*0.99+d*1.10=1.035*100 и 0<=a<=60, 0<=b<=80, 0<=c<=55 и 0<=d<=130.

Вы не говорите явно, но, вероятно, хотите получить целочисленные решения (то есть купленные количества должны быть целыми числами), следовательно, это целочисленная задача линейного программирования, а не задача линейного программирования. Несмотря на то, что проблемы ILP, как правило, сложны с точки зрения NP, в Интернете можно найти решатели и алгоритмы, которые легко решат эту небольшую проблему. Например, попробуйте GLPK.

Также обратите внимание, что грубая сила будет хорошо работать здесь; есть только 176851 комбинаций a,b,c,d, чтобы попробовать.