问最优配方问题

EN

这是精确覆盖问题，卡普在1972年的经典论文中证明NP是完整的21个问题之一，这篇论文确立了NP-完备的重要性。

维基百科的描述是：

给定一个集合X子集的集合S，一个精确的覆盖是一个子集合S*，使得X中的每一个元素都包含在两个子集*中。

最基本的问题是，在S和X的情况下，S是否包含X的确切覆盖？

这里X是你冰箱里的一套，S是菜谱的集合。任务是找到食谱的一个子集S*，这样X中的每个成分都被一个食谱所用。

确切的封面是已知的保持NP-完整，即使每个食谱不需要超过3种成分。如果每个菜谱有2个或更少的成分，则在二分图中找到一个最大匹配的多项式时间算法。

类似的问题，是否有覆盖S*，至少覆盖X的n个元素，也是NP-完全的。类似地，我们可以将其改写为一个优化问题:找到覆盖最大可能数量的元素的子集S*。求解这一优化问题的有效方法是求解NP-完全决策问题，至少与决策问题一样困难。

与NP-完全问题一样，可以这样说：

1. 一种适用于所有问题实例的好算法目前都是遥不可及的，而且很可能不存在。
2. 分支和绑定树搜索将很快找到一个很好的解决方案，为许多实例的问题，和小的实例。
3. 直截了当的方法(比如，总是选择含有最多可用成分的配方)可能会产生离最佳配方不远的结果。有很多关于这类事情的研究，应该不难发现一些。

维基百科还提到了唐纳德·算法，它通过将菜谱表示为矩阵的行，有效地执行了对解决方案空间(可能非常大)的彻底搜索。

听起来像是路径查找问题，您从节点X开始，希望以最少的成本移动几个步骤。

当你买东西的时候，成本就会增加，当你不买东西的时候，成本就会保持不变。

我建议在你找到冰箱空空如也的节点之前，给你一个充满洪水或极小最大的阿尔法贝塔。(在此之后，你无论如何都需要购买)

我要采取的方法是误差最小的方法。

1)创建一组符号来代表每一种食物。

2)用一串符号来表示冰箱里的东西。字符串被排序，多个项表示为多个符号。液体等应以多杯分数(即6x1/4杯牛奶)表示。

3)用相同的方式表示每个菜谱。

现在，做一个最小的错误模式匹配每个食谱字符串与冰箱字符串。

很久以前，我有过早期识别器的经验。我不知道这是否有帮助。