Этот вопрос закрыт для ответов, так как повторяет вопрос Как посчитать БЖУ?

Какой алгоритм использовать для подбора ингредиентов по составу?

Подскажите название алгоритма или как бы вы решали такую задачу?

В чём суть: есть целевой состав смеси, например a: 10%, b: 40%, c: 25%, ... и есть набор ингредиентов, которые включают в себя 1 или несколько из a, b, c в разных пропорциях. От программы требуется подобрать ингредиенты (то есть рассчитать какие именно и в каком количестве взять) таким образом, чтобы наилучшим (допускается приближенное решение) образом соответствовать целевому составу смеси.

То же самое, на примере кулинарии: надо получить смесь максимально близкую к такому составу: белков 10%, жиров 40%, углеводов 25%. Даны ингредиенты: сахар, масло, мука, сало, хлеб... (для всех известен БЖУ состав).

Целевой состав и доступные ингредиенты - это входные данные, ограничены сверху 10 штуками. То есть состав может быть от 1 до 10 позиций и набор ингредиентов от 1 до 10 штук.

ещё пример с решением

цель:
a: 10%, b: 40%, c: 25%

ингредиенты:
D: [a: 5, b: 10]
E: [c: 50]
F: [b: 20]

решение:
2D + 0.5E + 1F
  • Вопрос задан
  • 237 просмотров
Пригласить эксперта
Ответы на вопрос 2
trapwalker
@trapwalker
Программист, энтузиаст
Выглядит как NP-полная задача, чем-то напоминающая задачу укладки многомерного рюкзака или n--мерную задачу раскроя.
Но ваши ограничения в 10 компонентов позволяют решать эту задачу перебором. Тем более для кулинарии допустимо не слишком упарываться с точностью и ввести квантиикацию компонентов, чтобы иметь дело с целочисленными пропорциями.

Кстати, я так понимаю, что во всех ингридиентах и результирующем блюде должен быть ещё какой-то специальный ингридиент Z, который будет дополнять выделенные компоненты (например БЖУ) до 100%. Типа инертный наполнитель.
Допустим у вас есть полный перечень из N доступных ингридиентов. записанных в виде многомерных векторов.
Вам нужно взять из него подмножество M <= 10 и просуммировать с коэффициентами так, чтобы получилось равенство. Найти нужно x1, x2, x3...x10 - коэффициенты.

Фактически получится одно векторное уравнение с множеством переменных. А задача сводится к векторному преобразованию из пространства компонентов ингридиентов в подпространство ингридиентов.
Аналитически такое не решается. Да и точного решения не получится в принципе, поэтому нужно будет придумать как строить норму отклонения от пропорции и минимизировать эту норму.

Решать можно генетическими алгоритмами или роевыми.
Фитнес функцией будет норма отклонения от пропорции.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Как выяснили в комментариях, метрика будет sum_i w[i]^2 (actual[i]/ needed[i] - 1) ^ 2.

пусть x[i] - соклько i-ого продукта
Пусть a[i][j] - сколько в еденице i-ого продукта j-ого ингредиента. Тогда всего j-ого ингредиента будет sum_i a[i][j] x[i].

Тогда получаем следующую оптимизационную задачу:

Sum_j (sum_i A'[i][j] x[i] - C[i]) ^ 2 -> min
sum_i x_i = 1
x_i >= 0

Сумма всего приравнивается к 1, потому что иначе надо считать пропорции и получится вообще ужас-ужас.

A'[i][j], C[i] - какие-то числа, которые элементарно получаются из a[i][j], w[i] и needed[i].
A'[i][j] = a[i][j]*w[j]/needed[j]
C[j] = w[j] / needed[j];

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

Можно применить метод лагранжа, а точнее метод Каруша — Куна — Таккера

Сначала выразите x_1 = 1 -sum_j>1 x_j, подставьте во все уравнения и получите:
Sum_j (sum_i A''[i][j] x[i] - C'[i]) ^ 2 -> min
sum_i x_i -1 <= 0
x_i >= 0

Это уже похоже на то, что есть в википедии. Тут одно условие, поэтому будет один множитель лямбда. Надо составить функцию лагранжа, взять все ее производные по x_i и приравнять к 0. Полутчится система линейных уравнений.

Для условия жесткости придется рассмотреть 2 случая - лямбда - 0 или тогда sum_i x_i - 1 = 0

Прорешать оба случая (СЛАУ) и взять те, где все получается положительным.

Это что-то близкое к методу наименьших квадратов, но тут вводятся дополнительные переменные, чтобы боротся с ограничениями неотрицательности и общей суммы.
Ответ написан
Ваш ответ на вопрос

Вопрос закрыт для ответов и комментариев

Потому что уже есть похожий вопрос.
Похожие вопросы