我不确定我是否正确地确定了问题，但阅读背包问题似乎最接近我试图解决的问题：
厨师有几种不同数量的成分。例如：
8 个鸡蛋 3 根香肠 500 毫升牛奶 12 个草莓
有一个有限的食谱列表，每一个都包含不同数量的不同成分。成分的范围是有限的，所有食谱中每种成分的数量也是有限的。
每个食谱可能包含也可能不包含厨师所拥有的任何成分。
厨师希望尽可能多地用完他所有的原料，以尽量减少一份食谱的浪费。
有一种情况是，厨师想在 2 或 3 种不同的食谱中使用他的所有食材，而剩菜最少。
他的优化方案是什么？
编辑：我的问题是以下背包问题的更复杂版本 http://www.g12.cs.mu.oz.au/wiki/doku.php?id=simple_knapsack
如果我在您的 Q 中没有遗漏任何内容，这听起来不像是背包问题。每个配方中每种成分的数量是已知的，因此您的插槽大小不是变量。
如果我正确地阅读了您的 Q，您需要做的就是通过每个食谱运行成分，查看数量是否足够，如果是，计算要在该食谱中遗漏的成分的价值。具有最小这种正值的配方就是您的答案。直接访问成分列表需要 \theta(m*n) 时间 - m & n 成分和食谱的数量。
让我重写你的 Q 看看我是否理解正确：你有一组食谱 S，每一个都包含一个成分要求列表。厨师有一套配料，其中一些成分甚至可能为零。您想要确定 S 的一个子集，以便 S 中的每个食谱都可以通过厨师所拥有的成分来满足，同时最小化所谓的剩菜。
假设你有 1 个鸡蛋，5 根香肠；两个食谱： A. 香肠鸡蛋 - 1E1S；B. 巨型香肠-0E5S。所以可能的解决方案是 {A}.{B},{A,B}。{A}，剩下 4 根香肠；用 {B}，剩下 1 个鸡蛋，用 {A,B}，它实际上是非法或不可行的解决方案。
我的问题是：你如何评价剩下的？如果发生禽流感，鸡蛋可能价格过高，{B} 可能是首选。所以也许可以通过定价每种成分来定义一些加权和函数，比如f。
如果使用加权和，则可以将其视为多维 KP。这些项目是那些收据，具有多个“指标”，例如# of ingredients1（或说长度），# of ingredients2（或说宽度）......并且它们将被装进一个碰巧有多个维度（长度, width,...) 所以可行的包装必须满足其对每个维度的约束，即成分k的总使用量必须小于厨师所拥有的总成分 k。obj 是最小化f（重量）或 max f（用完的成分数量的价格）-互联网的总价格，或者只是第一部分。
据我所知，只要维度的数量（在你的情况下，成分）不高，这个问题是可以解决的。这有点像削减库存。