我们将图论和概率结合起来：

在第一天，构建一套所有可行的解决方案。让我们表示设置为A1 = {a1（1），a1（2），...，a1（n）}的解。

在第二天，您可以再次构建解决方案集A2。

现在，对于A2中的每个元素，您需要检查是否可以从A1的每个元素中达到（给定x％公差）。如果是这样-将A2（n）连接到A1（m）。如果无法从A1（m）中的任何节点访问它-您可以删除此节点。

基本上，我们正在建立一个连通的有向无环图。

图中所有路径的可能性均等。仅当从Am到Am + 1有一条边（从Am的节点到Am + 1的节点）时，您才能找到确切的解决方案。

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

通过为每个节点分配权重，该权重等于通向该节点的路径数，则无需保留所有历史记录，而仅保留前一天。

另外，请看一下非负值线性双phantine方程 -我刚才问过一个问题。可接受的答案是枚举每个步骤中所有组合的好方法。

这个问题是无法解决的。

假设您确切知道增加的项目数量是多少，而不仅仅是最大数量是多少。

用户有N个水果，而您有D天的猜测时间。

每天您将获得N个新变量，然后总共就有D * N个变量。

对于每一天，您只能生成两个方程式。一个方程是n_item * price的总和，另一个方程是基于已知比率的。如果它们都是独立的，则总共最多有2 * D个方程。

所有N> 2的2 * D <N * D

免责声明：由于我误读了问题的某些关键部分，因此暂时删除了我的答案并仔细阅读了该问题后，我的答案有了很大的改变。虽然仍然引用相似的主题和算法，但是在我尝试自己解决C＃中的某些问题后，答案得到了很大的改善。

好莱坞版

• 该问题是动态约束满足问题 （DCSP），是约束满足问题 （CSP）的变体。
• 如果值和数量范围不是很小，请使用Monte Carlo查找给定日期的潜在解决方案。否则，请使用蛮力找到所有可能的解决方案。
• 使用约束记录 （与DCSP相关），该记录已与前几天级联应用，以限制潜在的解决方案集。
• 交叉手指，根据概率瞄准并射击 （猜测）。
• （可选） Bruce Willis获胜。

原始版本

首先，我想说明一下我在这里看到的两个主要问题：

1. 数量众多的可能解决方案。仅知道项目数量和总价值，例如说3和143，将产生许多可能的解决方案。另外，要想让算法选择有效的解决方案而又不可避免地尝试使用无效的解决方案（总数不等于143），并非易事。

2. 当找到给定日期D _i的可能解时，必须找到一种方法，用{D _{i + 1} .. D _{i + n} }给出的附加信息消除潜在的解。

让我们为即将出现的示例奠定一些基础：

• 让整个游戏保持相同的物品价值。它可以是随机的，也可以由用户选择。
• 可能的项目值限制在[1-10]的非常有限的范围内，在该范围内，没有两个项目可以具有相同的值。
• 数量不能大于100。这表示：[0-100]。

为了更轻松地解决此问题， 我自由更改了一个约束 ，这使算法收敛速度更快：

• 该规则将覆盖“总数”规则：您可以在一天之内添加或删除总数在[1-10]范围内的任何数量的项目。但是，您不能添加或删除总数相同的项目，但不能超过两次。这也使游戏的最大生命周期为20天。

此规则使我们能够更轻松地排除解决方案。而且，对于非微小范围，渲染回溯算法仍然无效，就像您的原始问题和规则一样。

以我的拙见，该规则不是游戏的本质 ，而只是促进者，使计算机能够解决问题。

问题1：寻找潜在的解决方案

首先，可以使用蒙特卡洛算法解决问题1.找到一组潜在的解决方案。该技术很简单：为项目值和数量（在它们各自的可接受范围内）生成随机数。对所需数量的项目重复该过程。验证解决方案是否可接受。这意味着验证项目是否具有不同的值，并且总数等于我们的目标总数（例如143）。

尽管此技术具有易于实现的优点，但它也有一些缺点：

• 不能保证用户的解决方案会出现在我们的结果中。
• 有很多“遗漏”。例如，在我们的限制下，大约需要3,000,000次尝试才能找到1,000个潜在的解决方案。
• 这需要很多时间：在我的懒惰笔记本电脑上大约需要4到5秒钟。

如何克服这些缺点？好...

• 将范围限制为较小的值，然后
• 找到足够数量的潜在解决方案，以便用户解决方案很有可能出现在您的解决方案集中。
• 使用启发式方法更轻松地找到解决方案（稍后会详细介绍）。

请注意，限制范围的次数越多，蒙特卡洛算法的作用就越小，因为将没有足够的有效解决方案在合理的时间内对它们进行迭代。对于约束{3，[1-10]，[0-100]}，大约有741,000,000个有效解（不限于目标总值）。在那里可以使用Monte Carlo。对于{3，[1-5]，[0-10]}，大约只有80,000。无需使用蒙特卡洛；蛮力for循环会做得很好。

我相信问题1是您所说的约束满意度问题 （或CSP）。

问题2：限制一组可能的解决方案

鉴于问题1是CSP的事实，我将继续讨论问题2 ，通常将其称为动态CSP （或DCSP）。

当以某种方式更改问题的原始表述时，[DCSP]很有用，通常是因为要考虑的约束集因环境而变化。 DCSP被视为一系列静态CSP，每一个都是对前一个静态CSP的转换，可以在其中添加（限制）或删除（放松）变量和约束。

与CSP一起使用的一种可能对这个问题有用的技术称为约束记录 ：

• 随着环境中的每次更改（用户输入的D _{i + 1}值），查找有关新约束的信息：加减约束可能使用的数量是多少。
• 将约束应用于级联的每个前一天。涟漪效应可能会大大减少可能的解决方案。

为此，您每天需要获得一套新的可能的解决方案。使用蛮力或蒙特卡洛。然后，将D _i与D _i-1的解决方案进行比较，并仅保留在不违反约束的情况下可以取代前几天解决方案的解决方案。

您可能必须保留什么解决方案导致其他解决方案的历史记录（可能在有向图中）。约束记录使您能够记住可能的添加-删除数量并基于此拒绝溶液。

还有许多其他步骤可用来进一步改善您的解决方案。这里有一些想法：

• 记录在前几天解决方案中找到的项-值组合的约束。立即拒绝其他解决方案（因为项目值不得更改。）您甚至可以使用解决方案特定的约束为每个现有解决方案找到更小的解决方案集，以更早地拒绝无效解决方案。
• 每天生成一些“突变的”完整历史记录的解决方案，以“修复” D ₁解决方案集不包含用户解决方案的情况。您可以使用遗传算法根据现有的解决方案集找到突变种群。）
• 使用启发式方法轻松找到解决方案（例如，找到有效解决方案时，尝试通过替换周围的量来尝试找到该解决方案的变体。）
• 使用行为启发法来预测某些用户操作（例如，每项的数量相同，极端模式等）
• 用户输入新数量时，请继续进行一些计算。

考虑到所有这些，请尝试根据解决方案的出现和启发式方法确定排名系统，以确定候选解决方案。

我写了一个玩游戏的程序。当然，我必须使人的一面自动化，但是我相信我做到了这一点，以至于当我与一个真实的人对战时，我的方法不会失效。

我从机器学习的角度解决了这个问题，并将该问题视为隐藏的马尔可夫模型，其中总价格为观察值。我的解决方案是使用粒子过滤器。该解决方案是使用NumPy和SciPy用Python 2.7编写的。

我在注释中明确提出或在代码中隐含做出的任何假设。为了使代码以自动化方式运行，我还设置了一些其他约束。它并不是特别优化，因为我尝试在侧面理解而不是在速度方面犯错误。

每次迭代输出当前的真实数量和猜测值。我只是将输出通过管道传输到文件中，这样我就可以轻松对其进行查看。一个有趣的扩展是将输出绘制在2D（对于2个水果）或3D（对于3个水果）图上。然后，您将可以看到解决方案中的粒子过滤器已磨合。

更新：

调整后，编辑了代码以包含更新的参数。包括使用matplotlib（通过pylab）进行的绘图调用。绘图可在Linux-Gnome上进行，您的工作量可能会有所不同。默认的NUM_FRUITS为2，以支持绘图。只需注释掉所有pylab调用即可删除绘图，并能够将NUM_FRUITS更改为任何内容。

很好地估计由UnknownQuantities X Price = TotalPrice表示的当前fxn。在2D（2个水果）中，这是一条线；在3D（3个水果）中，这是一条平面。似乎数据太少，以至于粒子过滤器无法可靠地调整正确的数量。在粒子过滤器的顶部还需要更多的技巧，以真正收集历史信息。您可以尝试将粒子过滤器转换为2阶或3阶。

更新2：

我一直在玩我的代码。我尝试了很多事情，现在介绍了我将要编写的最终程序（开始厌倦这个想法）。

变化：

粒子现在使用浮点而不是整数。不知道这是否有任何有意义的作用，但这是一个更通用的解决方案。仅在进行猜测时才舍入到整数。

绘图将真实数量显示为绿色正方形，而当前猜测则显示为红色正方形。当前认为的粒子显示为蓝点（大小取决于我们对它们的相信程度）。这真的很容易看到算法的运行情况。 （绘图也经过测试，可以在Win 7 64位上运行）。

添加了用于关闭/打开数量更改和价格更改的参数。当然，两个“关闭”都不有趣。

它做得很好，但是，正如已经指出的，这是一个非常棘手的问题，因此很难找到确切的答案。关闭CHANGE_QUANTITIES会产生最简单的情况。您可以通过关闭CHANGE_QUANTITIES的2个水果来解决问题的难度。查看它以正确的答案进行磨合的速度，然后查看增加水果数量时的难度。

您还可以通过保持CHANGE_QUANTITIES的状态来了解难度，但是将MAX_QUANTITY_CHANGE的值从非常小的值（.001）调整为“较大的”值（.05）。

挣扎的一种情况是维数（一个水果的数量）接近零。因为它使用的是粒子的平均值来猜测，所以它总是会偏离硬边界（例如零）。

总的来说，这是一个很棒的粒子过滤器教程。

from __future__ import division
import random
import numpy
import scipy.stats
import pylab

# Assume Guesser knows prices and total
# Guesser must determine the quantities

# All of pylab is just for graphing, comment out if undesired
#   Graphing only graphs first 2 FRUITS (first 2 dimensions)

NUM_FRUITS = 3
MAX_QUANTITY_CHANGE = .01 # Maximum percentage change that total quantity of fruit can change per iteration
MAX_QUANTITY = 100 # Bound for the sake of instantiating variables
MIN_QUANTITY_TOTAL = 10 # Prevent degenerate conditions where quantities all hit 0
MAX_FRUIT_PRICE = 1000 # Bound for the sake of instantiating variables
NUM_PARTICLES = 5000
NEW_PARTICLES = 500 # Num new particles to introduce each iteration after guessing
NUM_ITERATIONS = 20 # Max iterations to run
CHANGE_QUANTITIES = True
CHANGE_PRICES = True

'''
  Change individual fruit quantities for a random amount of time
  Never exceed changing fruit quantity by more than MAX_QUANTITY_CHANGE
'''
def updateQuantities(quantities):
  old_total = max(sum(quantities), MIN_QUANTITY_TOTAL)
  new_total = old_total
  max_change = int(old_total * MAX_QUANTITY_CHANGE)

  while random.random() > .005: # Stop Randomly    
    change_index = random.randint(0, len(quantities)-1)
    change_val = random.randint(-1*max_change,max_change)

    if quantities[change_index] + change_val >= 0: # Prevent negative quantities
      quantities[change_index] += change_val
      new_total += change_val

      if abs((new_total / old_total) - 1) > MAX_QUANTITY_CHANGE:
        quantities[change_index] -= change_val # Reverse the change

def totalPrice(prices, quantities):
  return sum(prices*quantities)

def sampleParticleSet(particles, fruit_prices, current_total, num_to_sample):
  # Assign weight to each particle using observation (observation is current_total)
  # Weight is the probability of that particle (guess) given the current observation
  # Determined by looking up the distance from the hyperplane (line, plane, hyperplane) in a
  #   probability density fxn for a normal distribution centered at 0 
  variance = 2
  distances_to_current_hyperplane = [abs(numpy.dot(particle, fruit_prices)-current_total)/numpy.linalg.norm(fruit_prices) for particle in particles]
  weights = numpy.array([scipy.stats.norm.pdf(distances_to_current_hyperplane[p], 0, variance) for p in range(0,NUM_PARTICLES)])

  weight_sum = sum(weights) # No need to normalize, as relative weights are fine, so just sample un-normalized

  # Create new particle set weighted by weights
  belief_particles = []
  belief_weights = []
  for p in range(0, num_to_sample):
    sample = random.uniform(0, weight_sum)
    # sum across weights until we exceed our sample, the weight we just summed is the index of the particle we'll use
    p_sum = 0
    p_i = -1
    while p_sum < sample:
      p_i += 1
      p_sum += weights[p_i]
    belief_particles.append(particles[p_i])
    belief_weights.append(weights[p_i])

  return belief_particles, numpy.array(belief_weights)

'''
  Generates new particles around the equation of the current prices and total (better particle generation than uniformly random)
'''
def generateNewParticles(current_total, fruit_prices, num_to_generate):
  new_particles = []
  max_values = [int(current_total/fruit_prices[n]) for n in range(0,NUM_FRUITS)]
  for p in range(0, num_to_generate):
    new_particle = numpy.array([random.uniform(1,max_values[n]) for n in range(0,NUM_FRUITS)])
    new_particle[-1] = (current_total - sum([new_particle[i]*fruit_prices[i] for i in range(0, NUM_FRUITS-1)])) / fruit_prices[-1]
    new_particles.append(new_particle)
  return new_particles


# Initialize our data structures:
# Represents users first round of quantity selection
fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])
fruit_quantities = numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)])
current_total = totalPrice(fruit_prices, fruit_quantities)
success = False

particles = generateNewParticles(current_total, fruit_prices, NUM_PARTICLES) #[numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)]) for p in range(0,NUM_PARTICLES)]
guess = numpy.average(particles, axis=0)
guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)])

print "Truth:", str(fruit_quantities)
print "Guess:", str(guess)

pylab.ion()
pylab.draw()
pylab.scatter([p[0] for p in particles], [p[1] for p in particles])
pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s')
pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s')
pylab.xlim(0, MAX_QUANTITY)
pylab.ylim(0, MAX_QUANTITY)
pylab.draw()

if not (guess == fruit_quantities).all():
  for i in range(0,NUM_ITERATIONS):
    print "------------------------", i

    if CHANGE_PRICES:
      fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])

    if CHANGE_QUANTITIES:
      updateQuantities(fruit_quantities)
      map(updateQuantities, particles) # Particle Filter Prediction

    print "Truth:", str(fruit_quantities)
    current_total = totalPrice(fruit_prices, fruit_quantities)

    # Guesser's Turn - Particle Filter:
    # Prediction done above if CHANGE_QUANTITIES is True

    # Update
    belief_particles, belief_weights = sampleParticleSet(particles, fruit_prices, current_total, NUM_PARTICLES-NEW_PARTICLES)
    new_particles = generateNewParticles(current_total, fruit_prices, NEW_PARTICLES)

    # Make a guess:
    guess = numpy.average(belief_particles, axis=0, weights=belief_weights) # Could optimize here by removing outliers or try using median
    guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)]) # convert to integers
    print "Guess:", str(guess)

    pylab.cla()
    #pylab.scatter([p[0] for p in new_particles], [p[1] for p in new_particles], c='y') # Plot new particles
    pylab.scatter([p[0] for p in belief_particles], [p[1] for p in belief_particles], s=belief_weights*50) # Plot current particles
    pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s') # Plot truth
    pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s') # Plot current guess
    pylab.xlim(0, MAX_QUANTITY)
    pylab.ylim(0, MAX_QUANTITY)
    pylab.draw()

    if (guess == fruit_quantities).all():
      success = True
      break

    # Attach new particles to existing particles for next run:
    belief_particles.extend(new_particles)
    particles = belief_particles
else:
  success = True

if success:
  print "Correct Quantities guessed"
else:
  print "Unable to get correct answer within", NUM_ITERATIONS, "iterations"

pylab.ioff()
pylab.show()