Алгоритм для планирования меню, как реализовано на сайте?

Question

[Dragon1]

Имеется csv файл с рецептами (название блюда, количество калорий, количество белков, количество жиров, количество углеводов), хочу разобраться с алгоритмом для планирования меню на основании имеющихся рецептов, хочу сделать также, как на этом сайте https://www.eatthismuch.com, то есть,

• одно любое блюдо можно сгенерировать заново (и будет другое блюдо)
• всё меню можно сгенерировать заново
• стоимость меню нужно минимизировать
как эти пункты реализовать программно?

видел у google есть библиотека для оптимизации и решения проблем линейного программирования https://developers.google.com/optimization/lp/stig... но насколько я понимаю, результаты будут одни и те же? теоретически можно при каждом создании меню использовать случайным образом сгенерированную выборку (например из 100 000 рецептов брать 1 000)? или у вас есть другие идеи? хотелось бы услышать варианты как реализовать вышеперечисленные пункты.

Comments

[Adamos]

Так случайным образом или минимизировать стоимость?
Попахивает семиугольным треугольником.

[Dragon1]

Adamos,
1) стоимость нужно минимизировать
2) хочется, чтобы можно было на сайте нажать кнопку "сгенерировать ещё раз" и получить разные меню, которые +- подходят по количеству питательных веществ и цене, хорошо, у пользователя будет возможность ввести "погрешность" - на сколько % может отличаться итоговая цена.
Пока я вижу это так:
Из базы рецептов (например, 100 000) генерируется случайным образом выборка из 1 000 рецептов, затем на основании этих 1 000 рецептов генерируется минимизированное и сбалансированное меню, затем, если пользователь хочет изменить одно блюдо, то решается упрощённая задача линейного программирования (сколько должно быть калорий - количество калорий без этого блюда и т.д.), если пользователь хочет сгенерировать новое меню, то снова генерируется выборка из 1 000 рецептов и минимизируется стоимость.

[Adamos]

Dragon1, пальцем к носу:
1. Выбираете вообще случайным образом первое, второе и третье (или сколько там у вас блюд).
2 Сравниваете с эталоном цены и калорий, находите наиболее нарушающее этот эталон блюдо и заменяете его на аналогичное случайное.
3. Если за разумное число таких перестановок оптимум не нашелся - возвращаетесь к п. 1.
4. Повторяя все это до удовлетворения обоим показателям.
Потом, увидев уже на практике, какая херня получается, формируете более точное ТЗ и возвращаетесь к задаче снова ;)

Answer 1

[Wataru]

Если библиотека выдает всегда одно и то же решение из нескольких оптимальных, то можно случайным образом перемешивать входные данные. Просто все блюда тасуйте перед передачей данных в библиотеку. Это с большой вероятностью выдаст разные решения из оптимальных.

Comments

[Dragon1]

Библиотека google OR-tools выдаёт одно и то же решение, даже, если перемешивать входные данные.

[Wataru]

Dragon1, тогда можно попробовать поочередно исключать из входных данных одно из блюд в предвдущкм ответе.