我学习编程（Python和算法中的），并试图做一个项目，我觉得有趣。我设计了几个基本的Python脚本，但我不知道如何着手解决一个游戏，我想建立。

以下是本场比赛是如何工作的：

用户，将得到一个值的项目。例如

 苹果= 1
梨= 2
橙子= 3
 

然后，他们将有机会选择他们自己喜欢（即100苹果，梨20，和1个橙子）的任何组合。计算机得到的唯一输出是总值（在这个例子中，其目前$ 143页）。计算机将尝试猜测他们有什么。这显然​​也将不能够正确地得到第一个回合。

 价值量（第1天）值（第1天）
苹果1 100 100
梨2 20 40
橙3 1 3
总计121 143
 

下转用户可以修改自己的电话号码，但总量不超过5％（或者我们可以选择一些其他％，我将使用例如5％）。水果价格可以改变（随机），因此总价值可能会改变的基础上也（为简单起见，我不改变水果价格在这个例子中）。使用上面的例子，在游戏的2天中，用户返回$ 152的值，$ 164 3.天下面是一个例子。

 量（第2天）％的变化（第2天）值（第2天）数量（第3天）％的变化（第3天）值（第3天）
104 104 106 106
21 42 23 46
2 6 4 12
127 4.96％152 133 4.72％164
 

*（我希望表显示正确的，我不得不手动空间他们，所以希望它不只是做我的屏幕上，如果它不工作让我知道，我会试着上传截图）。

我想看看我能想出的数量是随着时间的推移（假设用户有耐心继续输入数字）的东西。我知道，现在我唯一的限制是总价值不能超过5％，所以我不能在5％以内的精度现在这样用户将永远进入它。

我迄今所做

下面是我的解决方案，到目前为止（不多）。基本上，我把所有的值，并计算出它们的所有可能的组合（我做了这部分）。然后，我把所有可能的组合，并把它们放在一个数据库字典（因此，例如为$ 143，有可能是一个字典项{苹果：143，梨：0，橙子：0} ..一路{苹果：0，梨：1，桔子：47}我这样做我每次拿到新号码的时间，所以我有所有的可能性列表

在此处，我坚持。采用上面的规则，我怎么能找出最佳的解决方案？我想，我需要一个健身功能，可以自动比较这两个天的数据并删除有$ P $超过5％的变化pvious天的数据。

问题：

所以我的问题与用户不断变化的总量，并且具有所有的概率名单，我应该如何处理呢？我需要什么学？是否有任何的算法在那里或理论，我可以使用适用？或者，要帮助我了解我的错误，你可以建议哪些规则，我可以添加，使这个目标可行的（如果不是在目前的状态。我想增加更多的水果和说，他们必须选择至少3个，等等。） ？另外，我只有一个模糊的认识遗传算法，但我想我可以在这里使用他们，如果是有什么我可以使用？

我非常非常渴望学习，所以任何建议或提示将不胜AP preciated（只是请你不要告诉我，这场比赛是不可能的）。

在此先感谢。

更新：获取反馈，这是很难解决的。所以，我想我会添加其他条件的游戏，不会有什么球员在做什么（游戏保持不变为他们）干扰，但每天水果的值更改价格（随机）。那会更容易解决？因为5％的运动和某些水果值改变内，只有少数组合的是可能随着时间的推移。第1天，一切皆有可能，并得到一个足够接近的范围几乎是不可能的，但作为水果的价格变化，用户只能选择5％的变化，那么不应该（一段时间内）的范围狭窄和狭窄。在上面的例子中，如果价格波动足够我想我可以蛮力，给了我一个范围来猜一个解决方案，但我试图找出是否有一个更好的解决方案或其他方案，以保持在缩小这个范围时间。

UPDATE2：阅读，并要求各地后，我相信这是跟踪水果价格的变化，以及总金额（加权最后一个数据点最重的），隐马尔可夫/维特比的问题。我不知道怎么虽然应用的关系。我觉得是这样的话，可能是错误的，但在至少我开始怀疑这是某种类型的机器学习问题。

UPDATE3：我创建了一个测试案例（较小的数字）和一台发电机，以帮助自动化用户生成的数据，我想从中创建一个图表看有什么更容易。 这里的code，以及哪些用户实际的水果量是总值和注释。

 ＃！的/ usr /斌/包膜蟒蛇
进口itertools

#Fruit价格数据
fruitPriceDay1 = {'苹果'：1，'梨'：2，'橘子'：3}
fruitPriceDay2 = {'苹果'：2，'梨'：3，'橘子'：4}
fruitPriceDay3 = {苹果：2，梨：4，橙子：5}

#generate可能性测试（Warning..will不具有大量扩展）
高清possibilityGenerator（target_sum，苹果，梨，桔子）：
    allDayPossible = {}
    计数器= 1
    apple_range =范围（0，target_sum + 1，苹果）
    pears_range =范围（0，target_sum + 1，梨）
    oranges_range =范围（0，target_sum + 1，橙子）
    对于I，J，K的itertools.product（apple_range，pears_range，oranges_range）：
        如果I + J + K == target_sum：
            currentPossible = {}
            #PRINT计数器
            #PRINT'苹果'，'：'，I /苹果，'，'，'梨'，'：'，J /梨，'，'，'桔子'，'：'，K /橙子
            currentPossible ['苹果'] = I /苹果
            currentPossible ['梨'] =焦耳/梨
            currentPossible ['桔子'] = K /桔子
            #PRINT currentPossible
            allDayPossible [计数器] = currentPossible
            反=计数器+1
    返回allDayPossible

用户水果的值返回＃合计总和
totalSumDa​​y1 = 26＃计算机不知道这一点，但用户数量是苹果：20，梨3，橘子0在当天的当前价格
totalSumDa​​y2 = 51＃计算机不知道这一点，但用户数量是苹果：21，梨3，橘子0在当天的当前价格
totalSumDa​​y3 = 61＃计算机不知道这一点，但用户数量是苹果：20，梨4，橙子1在当天的当前价格
图表= {}
图[DAY1'] = possibilityGenerator（totalSumDa​​y1，fruitPriceDay1 ['苹果']，fruitPriceDay1 ['梨']，fruitPriceDay1 ['橘子']）
图['DAY2'] = possibilityGenerator（totalSumDa​​y2，fruitPriceDay2 ['苹果']，fruitPriceDay2 ['梨']，fruitPriceDay2 ['橘子']）
图['第三天'] = possibilityGenerator（totalSumDa​​y3，fruitPriceDay3 ['苹果']，fruitPriceDay3 ['梨']，fruitPriceDay3 ['橘子']）
#sample字典= 1：{'桔子'：0，苹果：0，梨：0} .. 70：{'桔子'：8，苹果：26，梨：13}
打印图
 

解决方案

我们将结合图的理论和概率：

在第1天，建成集所有可行的解决方案。让表示设定为A1 = {A1（1）中，A（2），...，A1（n）}存储。

在第二天可以再次打造的解决方案设置A2。

现在，在A2每一个元素，你需要检查它是否可以从A1（给定的x％容差）的每个元素到达。如果是这样的 - 连接A2（N）至A1（M）。如果无法从任何节点到达A1（M） - 你可以删除这个节点

基本上，我们正在建设一个连接向无环图。

图中的所有路径都同样有可能。你可以找到一个确切的解决方案时，才会​​有从AM（在上午+ 1的节点从上午节点）。

当然，一些节点出现在比其他节点更多的路径。每个节点的概率可直接推导基于包含这个节点的路径的数目。

通过分配一个权重的每个节点，它等于，导致该节点的路径的数量，也没有必要将所有的历史，但只有previous天

另外，看看non-negative-values线性diphantine方程 - 一个问题，我问前一阵子。接受的答案是一个伟大的方式来enumarte在每个步骤中的所有组合。

I am learning programming (python and algo’s) and was trying to work on a project that I find interesting. I have created a few basic python scripts but I’m not sure how to approach a solution to a game I am trying to build.

Here’s how the game will work:

users will be given items with a value. For example

Apple = 1
Pears = 2
Oranges  = 3

They will then get a chance to choose any combo of them they like (i.e. 100 apples, 20 pears, and 1 oranges). The only output the computer gets is the total value(in this example, its currently $143). The computer will try to guess what they have. Which obviously it won’t be able to get correctly the first turn.

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

The next turn the user can modify their numbers but no more than 5% of the total quantity (or some other percent we may chose. I’ll use 5% for example.). The prices of fruit can change(at random) so the total value may change based on that also(for simplicity I am not changing fruit prices in this example). Using the above example, on day 2 of the game, the user returns a value of $152 and $164 on day 3. Here's an example.

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

*(I hope the tables show up right, I had to manually space them so hopefully its not just doing it on my screen, if it doesn't work let me know and I'll try to upload a screenshot).

I am trying to see if I can figure out what the quantities are over time(assuming the user will have the patience to keep entering numbers). I know right now my only restriction is the total value cannot be more than 5% so I cannot be within 5% accuracy right now so the user will be entering it forever.

What I have done so far

Here’s my solution so far(not much). Basically I take all the values and figure out all the possible combos of them(I am done this part). Then I take all the possible combos and put them in a database as a dictionary(so for example for $143, there could be a dictionary entry {apple:143, Pears:0, Oranges :0}..all the way to {apple:0, Pears:1, Oranges :47}. I do this each time I get a new number so I have a list of all possibilities.

Here’s where I’m stuck. Is using the rules above, how can I figure out the best possible solution? I think I’ll need a fitness function that automatically compares the two days data and removes any possibilities that have more than 5% variance of the previous days data.

Questions:

So my question with user changing the total and me having a list of all the probabilities, how should I approach this? What do I need to learn? Is there any algorithms out there or theories that I can use that are applicable? Or, to help me understand my mistake, can you suggest what rules I can add to make this goal feasible(if its not in its current state. I was thinking adding more fruits and saying they must pick at least 3,etc..)? Also, I only have a vague understanding of genetic algorithms but I thought I could use them here, if is there something I can use?

I'm very very eager to learn so any advice or tips would be greatly appreciated(just please don't tell me this game is impossible).

Thanks in advance.

UPDATE: Getting feedback that this is hard to solve. So I thought I'd add another condition to the game that won't interfere with what the player is doing(game stays the same for them) but everyday the value of the fruits change price(randomly). Would that make it easier to solve? Because within a 5% movement and certain fruit value changes, only a few combo's are probable over time. Day 1, anything is possible and getting a close enough range is almost impossible, but as the prices of fruits change and the user can only choose a 5% change, then shouldn't(over time) the range be narrow and narrow. In the above example, if prices are volatile enough I think I could brute force a solution that gave me a range to guess in, but I'm trying to figure out if there's a more elegant solution or other solutions to keep narrowing this range over time.

UPDATE2: After reading and asking around, I believe this is a hidden markov/Viterbi problem that tracks the changes in fruit prices as well as total sum(weighting the last data point the heaviest). I'm not sure how to apply the relationship though. I think this is the case and could be wrong but at the least I'm starting to suspect this is a some type of machine learning problem.

Update3: I am created a test case(with smaller numbers) and a generator to help automate the user generated data and I am trying to create a graph from it to see what's more likely. Here's the code, along with the total values and comments on what the users actually fruit quantities are.

#!/usr/bin/env python
import itertools

#Fruit price data
fruitPriceDay1 = {'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 fruits            
totalSumDay1=26 # computer does not know this but users quantities are apple: 20, pears 3, oranges 0 at the current prices of the day
totalSumDay2=51 # computer does not know this but users quantities are apple: 21, pears 3, oranges 0 at the current prices of the day
totalSumDay3=61 # computer does not know this but users quantities are apple: 20, pears 4, oranges 1 at the current prices of the day
graph = {}
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

We'll combine graph-theory and probability:

On the 1st day, build a set of all feasible solutions. Lets denote the solutions set as A1={a1(1), a1(2),...,a1(n)}.

On the second day you can again build the solutions set A2.

Now, for each element in A2, you'll need to check if it can be reached from each element of A1 (given x% tolerance). If so - connect A2(n) to A1(m). If it can't be reached from any node in A1(m) - you can delete this node.

Basically we are building a connected directed acyclic graph.

All paths in the graph are equally likely. You can find an exact solution only when there is a single edge from Am to Am+1 (from a node in Am to a node in Am+1).

Sure, some nodes appear in more paths than other nodes. The probability for each node can be directly deduced based on the number of paths that contains this node.

By assigning a weight to each node, which equals to the number of paths that leads to this node, there is no need to keep all history, but only the previous day.

Also, have a look at non-negative-values linear diphantine equations - A question I asked a while ago. The accepted answer is a great way to enumarte all combos in each step.