基于食材与食谱的最大产品数量最优组合计算方案问询

问题本质 #

这是典型的整数线性规划（ILP）问题：目标是最大化制作的产品总数量，约束条件为每种食材的总消耗量不超过可用库存，且每个食谱的制作次数为非负整数。

核心建模 #

设：

• 共有n个食谱，第i个食谱的制作次数为x_i（x_i ≥ 0，整数）
• 目标函数：Maximize(x₁ + x₂ + ... + xₙ)（总产品数最多）
• 约束条件：对每一种食材j，Σ(食谱i中j的用量 × x_i) ≤ 可用食材j的数量

实现方案（C#场景） #

1. 基础数据预处理 #

先把可用食材转换成字典，方便快速查询和计算：

// 把可用食材列表转成字典（名称->剩余数量）
var availableDict = availableIngredients.ToDictionary(ing => ing.Name, ing => ing.Quantity);

2. 暴力枚举+剪枝（适合食谱数量≤5的小规模场景） #

如果食谱数量不多，暴力枚举结合剪枝是最容易实现的方案：

步骤：

• 先计算每个食谱单独能制作的最大次数：对每个食谱，遍历其所有食材，取可用量/食谱用量的整数最小值，得到该食谱的最大可能制作数maxX_i
• 递归或嵌套循环枚举所有x₁~xₙ的组合，检查是否满足所有食材约束，记录总数量最大的组合
• 剪枝优化：如果当前已选的总次数 + 剩余食谱的最大可能总次数 ≤ 当前最优解，直接跳过该分支

示例代码：

// 存储最优组合：食谱名称->制作次数
private Dictionary<string, int> _bestCombination = new();
private int _maxTotal = 0;

public void FindBestCombination(List<Recipe> recipes, Dictionary<string, int> available)
{
    // 初始化最优解
    _bestCombination.Clear();
    _maxTotal = 0;

    // 先计算每个食谱的最大单独制作数
    var recipeMaxCounts = recipes.ToDictionary(r => r, r => GetMaxSingleRecipeCount(r, available));

    // 递归枚举所有组合
    EnumerateCombinations(recipes, recipeMaxCounts, new Dictionary<Recipe, int>(), available.ToDictionary(kv => kv.Key, kv => kv.Value), 0);
}

// 计算单个食谱最多能做多少次
private int GetMaxSingleRecipeCount(Recipe recipe, Dictionary<string, int> available)
{
    int max = int.MaxValue;
    foreach (var ing in recipe.Ingredients)
    {
        if (!available.TryGetValue(ing.Name, out int avail))
            return 0; // 缺食材，做不了
        max = Math.Min(max, avail / ing.Quantity);
    }
    return max;
}

// 递归枚举组合
private void EnumerateCombinations(List<Recipe> recipes, Dictionary<Recipe, int> recipeMaxCounts, Dictionary<Recipe, int> currentCombination, Dictionary<string, int> remainingIngredients, int currentTotal)
{
    int recipeIndex = currentCombination.Count;
    if (recipeIndex == recipes.Count)
    {
        // 更新最优解
        if (currentTotal > _maxTotal)
        {
            _maxTotal = currentTotal;
            _bestCombination = currentCombination.ToDictionary(kv => kv.Key.RecipeName, kv => kv.Value);
        }
        return;
    }

    var currentRecipe = recipes[recipeIndex];
    int maxPossible = recipeMaxCounts[currentRecipe];

    // 剪枝：当前总次数 + 剩余所有食谱的最大可能次数 <= 当前最优，直接跳过
    int remainingMax = recipes.Skip(recipeIndex).Sum(r => recipeMaxCounts[r]);
    if (currentTotal + remainingMax <= _maxTotal)
        return;

    // 枚举当前食谱的制作次数（从0到maxPossible）
    for (int count = 0; count <= maxPossible; count++)
    {
        // 检查食材是否足够
        var tempRemaining = remainingIngredients.ToDictionary(kv => kv.Key, kv => kv.Value);
        bool canMake = true;
        foreach (var ing in currentRecipe.Ingredients)
        {
            int required = ing.Quantity * count;
            if (tempRemaining[ing.Name] < required)
            {
                canMake = false;
                break;
            }
            tempRemaining[ing.Name] -= required;
        }

        if (!canMake)
            continue;

        // 加入当前组合
        currentCombination.Add(currentRecipe, count);
        // 递归处理下一个食谱
        EnumerateCombinations(recipes, recipeMaxCounts, currentCombination, tempRemaining, currentTotal + count);
        // 回溯
        currentCombination.Remove(currentRecipe);
    }
}

3. 大规模场景优化（食谱数量>5） #

如果食谱或食材数量较多，暴力枚举效率会很低，推荐使用整数线性规划求解库，比如Google OR-Tools：

using Google.OrTools.LinearSolver;

public Dictionary<string, int> FindBestCombinationWithORTools(List<Recipe> recipes, Dictionary<string, int> available)
{
    // 创建求解器
    var solver = Solver.CreateSolver("SCIP");
    if (solver == null)
        return new();

    // 定义变量：每个食谱的制作次数（整数，≥0）
    var variables = new Dictionary<Recipe, Variable>();
    foreach (var recipe in recipes)
    {
        variables[recipe] = solver.MakeIntVar(0.0, double.PositiveInfinity, recipe.RecipeName);
    }

    // 目标函数：最大化总数量
    var objective = solver.Objective();
    foreach (var var in variables.Values)
    {
        objective.SetCoefficient(var, 1);
    }
    objective.SetMaximization();

    // 添加约束：每种食材的总消耗 ≤ 可用量
    var ingredientNames = available.Keys.Union(recipes.SelectMany(r => r.Ingredients.Select(ing => ing.Name))).Distinct();
    foreach (var ingName in ingredientNames)
    {
        var constraint = solver.MakeConstraint(0.0, available.ContainsKey(ingName) ? available[ingName] : 0);
        foreach (var (recipe, var) in variables)
        {
            var ing = recipe.Ingredients.FirstOrDefault(i => i.Name == ingName);
            if (ing != null)
            {
                constraint.SetCoefficient(var, ing.Quantity);
            }
        }
    }

    // 求解
    var resultStatus = solver.Solve();
    if (resultStatus != Solver.ResultStatus.OPTIMAL)
        return new();

    // 提取结果
    var bestCombination = new Dictionary<string, int>();
    foreach (var (recipe, var) in variables)
    {
        bestCombination[recipe.RecipeName] = (int)var.SolutionValue();
    }
    return bestCombination;
}

执行后食材扣除逻辑 #

得到最优组合后，遍历每个食谱的制作次数，按用量扣除对应食材：

public void DeductIngredients(Dictionary<string, int> bestCombination, List<Recipe> recipes, List<Ingredient> availableIngredients)
{
    var availableDict = availableIngredients.ToDictionary(ing => ing.Name, ing => ing);
    foreach (var (recipeName, count) in bestCombination)
    {
        if (count == 0)
            continue;
        var recipe = recipes.First(r => r.RecipeName == recipeName);
        foreach (var ing in recipe.Ingredients)
        {
            availableDict[ing.Name].Quantity -= ing.Quantity * count;
        }
    }
}

示例数据验证 #

以你提供的3个食谱为例，假设可用食材为：

• Peppers: 1000g, Tomatoes: 1500g, Carrots: 300g, Salt: 200g, Sugar: 150g, Eggplant: 900g, Onion: 150g, Garlic: 75g, Potatoes: 400g

通过计算，最优组合可能是：

• recipe1: 3次（消耗Peppers900, Tomatoes900, Carrots300, Salt150, Sugar150）
• recipe2: 0次
• recipe3: 2次（消耗Potatoes400, Tomatoes400, Eggplant600, Salt50, Onion100, Garlic50）
  总产品数5，且所有食材消耗都在可用范围内。

内容的提问来源于stack exchange，提问作者Fallon