问需要一种算法方法来计算膳食计划

EN

与穷举计数相比，mcdowella分支和定界解将是一个很大的改进，但它可能还需要几千年的时间。这是真正最好通过ILP求解器来解决的问题。

假设一顿饭的配料是由Ri ={ Ri，Ri，.，Ri x Ri] }给出的，那么您可以将问题编码如下：

• 为每个成分创建一个整数变量xi 1 <= i <= 100。这些变量中的每一个都应该被限制在0，1的范围内。
• 为每顿饭创建一个整数变量，1 <= i <= 50。这些变量中的每一个都应该被限制在0，1的范围内。
• 对于每顿饭，为1 <= x[Ri]的<= j <= _<=_Ri_建立_这将保证，如果我的所有食材都包括在内的话，我们只能把我的食材设定为1。
• 添加一个约束，所有xi的和必须为<= 32。
• 最后，目标函数应该是整个彝族的总和，我们应该努力使其最大化。

解决这个问题将产生所有变量xi: 1的赋值，意味着成分应该包括在内，0意味着不应该包含。

我的感觉是，像CPLEX或Gurobi这样的商业ILP解决器可能会在毫秒内解决150个可变的ILP问题；即使是像解算这样的自由可用的求解器(通常速度要慢得多)，也不会有任何问题。在看似要花很长时间的情况下，你仍然可以解决LP放松问题，这将是非常快的(毫秒)，并会给你(a)一个上限，最多可以准备的食物数量和(b)在可变值中的“提示”：虽然xi值一般不是0或1，但接近1的值暗示了应该包含的成分，而接近0的值则暗示着没有用的成分。

这将有一个定界解决方案，但它可能太昂贵，以获得确切的答案- ILP建议的可能更好- LP松弛，这可能是一个更好的启发比这里提出的松弛，并且ILP的求解器将得到很大的优化。

基本思想是，首先对部分解树进行递归深度搜索，然后每次扩展它们。一旦您恢复到足够深入到完全填充的解决方案，您就可以开始跟踪到到目前为止找到的最佳解决方案。如果我给你贴上A，B，C，D.部分解决方案是长度为<= 32的成分列表。从零长解开始，然后当你访问一个部分解时，你会考虑ABCD，ABCE，.以此类推，并可能访问其中的一些。

对于每个部分解决方案，您计算出该解决方案的任何后代所能达到的最大分数。对此有一个准确的认识是很重要的。这里有一个建议--假设你有一个长度为20的部分解决方案。这就剩下12种配料可供选择，所以你可以做的最好的方法是，让所有不超过12种配料的菜肴

现在，当您考虑将部分解决方案ABC扩展到ABCD或ABCE或ABCF时.如果到目前为止，您已经找到了最好的解决方案，那么您可以忽略所有的扩展，这些扩展不可能比目前最好的解决方案得分更高--这意味着您不需要考虑所有可能组合的32种成分。

一旦确定了哪些扩展可能包含新的最佳答案，递归搜索就应该继续进行这些可能的扩展中最有希望的扩展，因为这是迄今为止最有可能找到更好的最佳解决方案的扩展。

实现这种快速的一种方法是巧妙地对其进行编码，这样递归向上和向下只意味着对现有数据结构的小改动，而这种变化通常是在下降的过程中进行的，而在向上的过程中则是反向的。

另一种方法是偷工减料。一个显而易见的方法是，当你没有时间的时候停下来，去寻找目前为止找到的最好的解决方案。另一种方法是更积极地放弃部分解决方案。如果到目前为止你的分数是100，你可以放弃分数不能超过110的部分解决方案。这加快了搜索的速度，而且你知道，尽管你可能有一个比100更好的答案--不管你错过了什么，都不可能比110更好。

解一些离散的数学哈？好吧，这里是维基。

你也没有考虑到任何关于数量的因素。例如，面粉会在很多油炸食谱中使用，但是买10磅面粉可能不是很好。而且，对于解决方案所需的某些成分，成本可能会令人望而却步。更别提所有的东西都有很多成分。(牛奶、水、盐、胡椒、糖之类的东西)

在现实中，这种程度的优化可能是不必要的。但我不会就此提供关系上的建议。

至于新的解决办法：

我建议你找出很多你想做的，用什么做的，然后写一个程序来建议其他的东西。