поиск оптимальной суммы столбцов

[yurican]

Но, чтобы бизнес не поменял требования на ходу несколько раз

Долго думал, какие требования могут поменяться со временем.. вроде бы никакие.

mserg, а какие, например, _поменявшиеся_требования_ может "переварить" lp_solve? Хотя бы один пример.

[mserg]

Примеры изменений:
* Увеличение количества типов товаров
* Заказ не поштучно, а некоторого количества каждого из товаров
* Неполная матрица (некоторые поставщики не поставляют некоторые товары)
* Скидки при заказе нескольких товаров у одного продавца
* Количество поставщиков в задаче не фиксировано, а указан их допустимый диапазон.
И т.д. lp_solve изменения «не переваривает», их дешевле туда вносить, нежели в алгоритм.

В конце концов, что использовать – это Ваше дело. Я же не знаю деталей бизнеса и что там может измениться, и поэтому мои советы могут быть излишними/неподходящими.

[yurican]

mserg, спасибо за целый список вариантов!)

Ничего этого однозначно не будет. Однозначно.

Видимо, тогда всё же полностью подойдёт динамическое программирование. Единственное -- я не знаю производительность (нагрузку на сервер) как lp_solve, так и решения с помощью динамического программирования. Как вы считаете, что эффективней?

Друзья, у вас такие светлые головы!)

[mserg]

Динамическое программирование должно быть быстрее и устойчивее. Но условие по количеству продуктов "обычно от 3 до 10" весьма подозрительно... Нужно твердо знать, так как, скажем при 20 продуктах динамическому программированию каюк.
Прикидочно, линейное программирование потребует секунды или десятки секунд при матрице в 30000 элементов.

20 еще выдержит. это всего лишь 5000 раз пробежаться по массиву размера 4*2^20 = 4Mb, который скорее всего даже целиком в L2 кеш влезет на xeon'ах. ну, будет может полминуты-минуту работать

Прикидочно, линейное программирование потребует секунды или десятки секунд при матрице в 30000 элементов.

а целочисленное программирование?

[mserg]

Да, действительно, а как же целочисленное программирование?

[yurican]

наверное, Гость имел в виду "динамическое программирование"