更新（2020年7月）：这个问题已经有9年的历史了，但我仍然对此深感兴趣。在这段时间里，机器学习（RNN、CNN、GAN等）、新方法和廉价的GPU已经崛起，启用了新的方法。我认为重新审视这个问题会很有趣，看看是否有新的方法。

我正在学习编程（Python和算法），并试图从事一个我觉得有趣的项目。我已经创建了一些基本的Python脚本，但我不知道如何解决我正在尝试构建的游戏。

游戏的运作方式如下：

用户将获得带有价值的物品。例如，

Apple = 1Pears = 2Oranges  = 3

然后他们将有机会选择他们喜欢的任何组合（例如100个苹果，20个梨和一个橙子）。计算机获得的唯一输出是总价值（在这个例子中，目前是$143）。计算机将尝试猜测他们有什么。显然，它在第一轮中无法正确猜到。

         Value    quantity(day1)    value(day1)Apple      1        100                100Pears      2         20                 40Orange     3          1                  3Total               121                143

下一轮，用户可以修改他们的数字，但不能超过总数量的5%（或我们可能选择的其他百分比。我将使用5%作为例子）。水果的价格可能会随机变化，因此总价值也可能因此变化（为了简单起见，在这个例子中我没有改变水果价格）。使用上面的例子，在游戏的第2天，用户返回的值为$152，第3天为$164。以下是一个例子：

Quantity (day2)   %change (day2)    Value (day2)   Quantity (day3)   %change (day3)   Value(day3) 104                                 104            106                                106  21                                  42             23                                 46   2                                   6              4                                 12 127               4.96%             152            133               4.72%            164

*(我希望表格能正确显示，我不得不手动调整它们的位置，希望不只是在我的屏幕上显示，如果没有正确显示，请告诉我，我会尝试上传一个截图。)

我正在尝试看看我是否能随着时间的推移找出数量是多少（假设用户有耐心继续输入数字）。我知道目前我的唯一限制是总价值不能超过5%，所以我现在不能达到5%的准确度，所以用户将永远输入它。

我目前所做的

这是我目前的解决方案（不多）。基本上，我获取所有值并找出它们的所有可能组合（我已经完成了这部分）。然后我将所有可能的组合放入数据库中作为字典（例如，对于$143，可能有一个字典条目{apple:143, Pears:0, Oranges :0}…一直到{apple:0, Pears:1, Oranges :47}）。每次我得到一个新数字时，我都会这样做，所以我有一份所有可能性的列表。

我卡在这里。使用上面的规则，我如何找出最佳可能的解决方案？我认为我需要一个适应度函数，自动比较两天的数据，并删除任何与前一天数据超过5%差异的可能性。

问题：

所以我的问题是，用户改变总数而我有一份所有可能性的列表，我应该如何处理这个问题？我需要学习什么？是否有任何适用的算法或理论？或者，为了帮助我理解我的错误，你能建议我可以添加哪些规则来使这个目标可行（如果它目前的状态不可行。我在考虑添加更多水果并说他们必须至少选择3种，等等…）？另外，我对遗传算法只有模糊的了解，但我认为我可以在这里使用它们，如果有什么我可以用的话？

我非常非常渴望学习，所以任何建议或提示都将不胜感激（请不要告诉我这个游戏是不可能的）。

更新：得到反馈说这很难解决。所以我想我可以添加另一个条件到游戏中，不会干扰玩家在做什么（游戏对他们来说保持不变），但每天水果的价格会随机变化。这会使它更容易解决吗？因为在5%的变动范围内和某些水果价值变化的情况下，随着时间的推移，只有少数组合是可能的。

第一天，任何事情都是可能的，找到一个足够接近的范围几乎是不可能的，但随着水果价格的变化和用户只能选择5%的变化，那么（随着时间的推移）范围不应该越来越窄吗。在上面的例子中，如果价格波动足够大，我认为我可以通过蛮力找到一个范围来猜测，但我正在尝试找出是否有更优雅的解决方案或其他解决方案来随着时间的推移不断缩小这个范围。

更新2：经过阅读和询问，我相信这是一个隐藏的马尔可夫/维特比问题，它跟踪水果价格的变化以及总和（最重视最后一个数据点）。我不知道如何应用这种关系。我认为这是这种情况，可能是错的，但至少我开始怀疑这是一个某种类型的机器学习问题。

更新3：我创建了一个测试案例（使用较小的数字）和一个生成器来帮助自动化用户生成的数据，我正在尝试从中创建一个图表来看看什么更有可能。

这是代码，连同总值和关于用户实际水果数量的评论。

#!/usr/bin/env pythonimport itertools# Fruit price datafruitPriceDay1 = {'Apple':1, 'Pears':2, 'Oranges':3}fruitPriceDay2 = {'Apple':2, 'Pears':3, 'Oranges':4}fruitPriceDay3 = {'Apple':2, 'Pears':4, 'Oranges':5}# Generate possibilities for testing (warning...will not scale with large numbers)def possibilityGenerator(target_sum, apple, pears, oranges):    allDayPossible = {}    counter = 1    apple_range = range(0, target_sum + 1, apple)    pears_range = range(0, target_sum + 1, pears)    oranges_range = range(0, target_sum + 1, oranges)    for i, j, k in itertools.product(apple_range, pears_range, oranges_range):        if i + j + k == target_sum:            currentPossible = {}            #print counter            #print 'Apple', ':', i/apple, ',', 'Pears', ':', j/pears, ',', 'Oranges', ':', k/oranges            currentPossible['apple'] = i/apple            currentPossible['pears'] = j/pears            currentPossible['oranges'] = k/oranges            #print currentPossible            allDayPossible[counter] = currentPossible            counter = counter +1    return allDayPossible# Total sum being returned by user for value of fruitstotalSumDay1=26 # Computer does not know this but users quantities are apple: 20, pears 3, oranges 0 at the current prices of the daytotalSumDay2=51 # Computer does not know this but users quantities are apple: 21, pears 3, oranges 0 at the current prices of the daytotalSumDay3=61 # Computer does not know this but users quantities are apple: 20, pears 4, oranges 1 at the current prices of the daygraph = {}graph['day1'] = possibilityGenerator(totalSumDay1, fruitPriceDay1['Apple'], fruitPriceDay1['Pears'], fruitPriceDay1['Oranges'] )graph['day2'] = possibilityGenerator(totalSumDay2, fruitPriceDay2['Apple'], fruitPriceDay2['Pears'], fruitPriceDay2['Oranges'] )graph['day3'] = possibilityGenerator(totalSumDay3, fruitPriceDay3['Apple'], fruitPriceDay3['Pears'], fruitPriceDay3['Oranges'] )# Sample of dict = 1 : {'oranges': 0, 'apple': 0, 'pears': 0}..70 : {'oranges': 8, 'apple': 26, 'pears': 13}print graph

回答：

我们将结合图论和概率：

在第一天，构建所有可行解的集合。我们将解集表示为A1={a1(1), a1(2),…,a1(n)}。

在第二天，你可以再次构建解集A2。

现在，对于A2中的每个元素，你需要检查它是否可以从A1中的每个元素到达（给定x%的容忍度）。如果可以 – 连接A2(n)到A1(m)。如果它不能从A1(m)中的任何节点到达 – 你可以删除这个节点。

基本上我们正在构建一个连接的有向无环图。

图中的所有路径都是同样可能的。只有当从Am到Am+1（从Am中的一个节点到Am+1中的一个节点）只有一条边时，你才能找到一个确切的解决方案。

当然，一些节点出现在比其他节点更多的路径中。每个节点的概率可以直接根据包含该节点的路径数量来推断。

通过为每个节点分配一个权重，等于通向该节点的路径数量，就不需要保留所有历史记录，只需保留前一天的记录即可。

另外，请查看非负值线性丢番图方程 – 这是我之前问过的一个问题。接受的答案是枚举每一步的所有组合的好方法。