最接近 x 卡路里类型的膳食计划算法

Question

我有一个问题，我需要制定膳食计划：

• x 每天的用餐次数（例如 5）
• x 计划中的膳食类型数量（例如 2 份早餐、2 份小吃和 1 份午餐）
• 膳食计划中的卡路里数（例如 2000）
• 不应该重复用餐

给定的数据是一个字典列表（超过 100,000 个单元），其结构如下：

{'title': 'Cannellini Bean and Asparagus Salad with Mushrooms', 'types': ['side dish', 'lunch', 'main course', 'salad', 'main dish', 'dinner'], 'calories': 482}

算法的输出应该是最接近 x 卡路里的 x 餐及其相关膳食类型的列表。

我不知道从哪里开始解决这个问题，欢迎任何算法类型或实现。

Answer 1

这个问题是NP困难的。然而，这并不意味着我们无法解决它：我们通常可以使用约束规划技术来快速解决此类问题。

您的约束的一些参数：

NUM_MEALS = 5
MEAL_TYPES = ['breakfast', 'dinner', 'lunch', 'snack']
REQUIRED_MEALS = [1, 1, 1, 2]
TARGET_CALORIES = 2_000
TOLERANCE = 50

我假设有四种膳食类型，每种膳食类型都需要在膳食计划中出现特定的次数（这里，早餐、晚餐和午餐都需要出现一次，并且我们需要两种零食）。我们还有 2K 总卡路里的热量需求，以及我们认为可以接受的容忍度：该范围内的任何食物都[2K - 50, 2K + 50]可以。我们需要一点宽容，因为并不总是能够找到精确达到 2K 卡路里的完美膳食。请随意将容差更改为您认为合理的任何内容。

生成一些适当大小的随机数据：

def make_random_meal_options():
    options = []

    for _ in range(100_000):
        calories = np.random.randint(100, 1_000)
        num_types = np.random.randint(1, len(MEAL_TYPES))
        types = np.random.choice(MEAL_TYPES, num_types, replace=False)

        options.append(dict(calories=calories, types=types))

    # List of dictionaries with keys 'calories' and 'types'
    return options

meal_options = make_random_meal_options()

我们生成 100K 个代表膳食的字典：每个字典都有一些卡路里（在 中统一[100, 1000]）和一组它可以满足的膳食类型。

如果我们将卡路里作为 numpy 数组，以及匹配膳食和膳食类型的布尔矩阵，将会很有帮助：

import numpy as np

calories = np.array([option['calories'] for option in meal_options])

# Element (i, j) == True iff meal i has meal type j, and False otherwise.
meal_types = np.empty((len(meal_options), len(MEAL_TYPES)), dtype=bool)

for i, option in enumerate(meal_options):
    for j, meal_type in enumerate(MEAL_TYPES):
        meal_types[i, j] = meal_type in option['types']

为了指定模型，我将使用 Google OR-Tools 的CP 求解器，因为这是免费提供的软件。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Decision variables, one for each meal and meal type: meal[i, j] is 1 iff
# meal i is assigned to meal type j, and 0 otherwise.
meal_vars = np.empty((len(meal_options), len(MEAL_TYPES)), dtype=object)

for i in range(len(meal_options)):
    for j in range(len(MEAL_TYPES)):
        meal_vars[i, j] = model.NewBoolVar(f"meal[{i}, {j}]")

# We want the overall caloric value of the meal plan to be within bounds.
lb, ub = [TARGET_CALORIES - TOLERANCE, TARGET_CALORIES + TOLERANCE]
model.AddLinearConstraint(calories @ meal_vars.sum(axis=1), lb, ub)

for j, meal_type in enumerate(MEAL_TYPES):
    # Need the required amount of meals of each type.
    model.Add(meal_types[:, j] @ meal_vars[:, j] == REQUIRED_MEALS[j])

for i in range(len(meal_options)):
    # Each meal can only be selected once across all meal types.
    model.Add(meal_vars[i, :].sum() <= 1)

# Need NUM_MEALS meals in the meal plan
model.Add(meal_vars.sum() == NUM_MEALS)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"Solving took {solver.WallTime():.2f} seconds")

    for i in range(len(meal_options)):
        for j in range(len(MEAL_TYPES)):
            if solver.Value(meal_vars[i, j]) > 0:
                option = meal_options[i]
                cal = option['calories']
                mt = MEAL_TYPES[j]

                print(f"Selected meal {i} with {cal} calories for {mt}.")
else:
    print("No solution found.")

这是一个约束编程模型，具有用于将膳食分配给膳食类型的布尔选择变量（是/否），以及对这些变量的几个约束：在所有膳食类型中，每种膳食只能选择一次，所选膳食需要总和为在耐受范围内的热量值，每种类型的膳食都需要足够，而且我们需要精确的NUM_MEALS膳食。

当我将种子固定为 后在我的机器上运行它时42，我得到：

Solving took 19.07 seconds
Selected meal 1682 with 100 calories for lunch.
Selected meal 76138 with 999 calories for snack.
Selected meal 86843 with 100 calories for breakfast.
Selected meal 95861 with 100 calories for snack.
Selected meal 99987 with 706 calories for dinner.

运行时间远不到一分钟，而且膳食计划有效。尽管这个问题是 NP 困难的，但它是可以解决的。