Построение меню на основе требований к питанию

Question

Мне нужно создать семь ежедневных меню. Меню состоит из завтрака, обеда, ужина и трех закусок. У меня есть несколько сотен рецептов, взятых с fatsecret.com. Каждый рецепт содержит информацию о питании, такую ​​как: калории, жир, натрий, клетчатка. Каждое ежедневное меню ограничивается:

Calories: 1500 
Sodium: 200g 
Fiber: 32g 
Fat: 30g 

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

Я думаю о древовидной структуре, которая поддерживает каждый раз, когда создается неправильный выбор меню и пробует другую ветку, но я застрял на этом. Любая помощь приветствуется.

Answer 1

Вы можете индексировать рецепты примерно как k-d tree - это позволит вам эффективно устранять рецепты, которые нельзя комбинировать с текущим выбором меню, и позволит вам применять эвристику для улучшения шансов найти правильную комбинацию (например «обед не может составлять более 50% ежедневных калорий»)

Answer 2

Я предложу несколько возможных подходов.

Примеры комбинации

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

Используйте подход Вдохновленный динамического программирования

Я говорю «вдохновлен» динамического программирования («ДП»), как я считаю DP, как исключительно с техникой оптимизации. Не нужно читателю знать о ДП, но для тех, кто это делает, «этапами» будут питание, а «состояния» на каждом этапе будут сочетанием питательных ценностей, предоставляемых рецептами для всех блюд до и включая питание, связанное с данным этапом.

Для каждого диетического пункта, предположим, что мы можем круглый:

• калорий до ближайшего 20;
• натрий до ближайшей 5 г;
• волокно и жир каждый до ближайшего грамма.

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

Это дает нам 76 * 41 * 33 * 31 => 3,187,668 приемлемых комбинаций из четырех питательных веществ.

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

{ calories: 460, sodium: 55, fibre: 4, fat: 6 } 

Пусть r[0] быть хэш с элементами k=>v, где ключами являются массивами [calories, sodium, fibre, fat], один для каждой комбинации:

• calories между 0 и 1500, в упаковке 20;
• sodium, между 0 и 200 в кратных 5;
• fibre, между 0 и 32; и
• fat, между 0 и 30.

Для данного ключа [calories, sodium, fibre, fat], ассоциированное значение представляет собой набор рецептов для еды 0, которые предусматривают, что данная комбинация ингредиентов.

Мы просто используем все рецепты, которые доступны для приема пищи в ноль. Если данный рецепт соответствует питательному содержимому, заданному ключом k, мы видим, что связанное значение r[0][k] уже содержит достаточное количество рецептов (например, 7). Если это не так, мы добавляем этот рецепт к значению (array).

Предположим, что мы выполнили вычисления, которые я собираюсь описать для питания 0, 1, 2,..., i. Мы вычислили r[j], 0 <= j <= i, где r[j], является хэш-ключей, которые представляют собой комбинации четырех питательной ценности и значения которого (, пожалуйста, прочтите следующее очень внимательно) набор рецептов для всех блюд 0, 1, 2,..., i, которые приводят к питательная значения, заданные ключом.

Теперь вычислим r[j+1], выполнив следующие шаги.

Для каждого ключа k в r[j]:

k = [calories, sodium, fibre, fat] 

мы рассмотрим каждый рецепт для еды j+1, характеризующаяся:

[r_calories, r_sodium, r_fibre, r_fat]  

и вычислить

k' = [calories+r_calories, sodium+r_sodium, fibre+r_fibre, fat+r_fat] 

Если какой-либо из этих четырех значения превышают соответствующие максимальные суточные пределы это, рецепт нельзя использовать для этого конкретного ключа. Если значения находятся в пределах лимита, это будет ключ от r[j+1]. Значение, связанное с этим ключом, r[j+1][k'] - это набор всех рецептов для всех блюд до и включая питание j+1, которые приводят к питательным значениям, заданным этим ключом. Если это значение не включает достаточное количество (например, не менее 7) рецептов для приема пищи j+1 (вместе с рецептами для более ранних блюд), мы добавляем рецепт, который мы рассматриваем, вместе со всеми рецептами, указанными r[j][k]. Затем мы повторяем это для всех возможных рецептов еды. По завершении мы повторяем эти шаги для каждого из других ключей в r[i] (из которых могут быть миллионы).

Обратите внимание, что на самом деле не нужно было хранить все рецепты для всех блюд до и в том числе еды j+1 в значении (массиве) r[j+1][k']. Скорее всего, мы просто будем хранить рецепты для еды j+1 и для каждого из них - указатель на связанный ключ в r[j].

У каждого r[j] будет самое большее 3 187 668 ключей, но на самом деле их число будет значительно меньше. Если бы было, скажем, 100 возможных рецептов для каждого приема пищи, мы должны были бы выполнить максимум 3187668 * 100 => 318,766,800 этих операций за каждое из пяти блюд после первого. Важно отметить, что количество вычислений увеличивается (только) линейно с количеством приемов пищи. Я бы ожидал, что это будет управляемо с вычислительной точки зрения.

Все значения в r[5] представляют наборы рецептов для всех шести блюд, которые удовлетворяют максимальным ежедневным питательным значениям. Если комбинации не найдены, то не существует.

Answer 3

Если ограничения не слишком плотные, то может использоваться Metropolis--Hastings sampling. (В противном случае вам понадобится динамическая программа Cary или, возможно, целочисленное программирование.) Предвзятость, введенная сэмплированием, должна подтолкнуть меню к выполнимости, гарантируя случайность.

Инициализируйте меню, выбирая каждый курс равномерно в случайном порядке. Повторно сделайте следующий шаг, пока меню не станет приемлемым. Начиная с текущего меню, выберите курс равномерно случайным образом и рецепт равномерно случайным образом, выведя предлагаемое меню, используя этот рецепт для этого курса. Определите счет меню, которое будет следующим.

max(calories - 1500, 0)  max(sodium - 200, 0) max(32 - fiber, 0) max(fat - 30, 0) 
0.99      0.95      0.7     0.7 

(Основания показателей заслуживают некоторого экспериментирования. Я предполагаю, что избыток калорий, натрия и жира плохо, как недостаточное волокно.) Держите предлагаемое меню, если и только если rand (единый поплавок в [0.0, 1.0)) меньше, чем оценка предлагаемого меню, деленная на оценку текущего меню.