相关疑难解决方法(0)

我有一个符合以下规则的游戏:

• 用户获得水果价格并且每次都有机会在他们的水果篮中购买或出售物品.

• 一次转动,用户的篮子总变化不会超过10%.

• 水果价格每天都在变化,当乘以水果篮中的物品数量时,篮子的总价值也会相对于每天的水果价格变化而变化.
• 该计划仅给出所有水果的当前价格和篮子的当前价值(水果的当前价格*篮子中所有项目的数量).
• 根据这2个输入(所有水果价格和篮子总价值),该程序试图猜测篮子中的物品.
• 一个篮子不能容纳超过100件物品但是空位可以是空的
• 玩家可以多次转弯.

我的目标是尽可能以低廉的价格准确地猜测(如果没有蛮力),并且如果有数以千计的新果实,则进行扩展.

我很难找到答案,但在我看来,并不难.如果我有下表.我可以在第1天学习并获得以下数据:

Apple   1
Pears   2
Oranges 3

Basket Value = 217

我可以做一个餐巾计算的背面并假设,篮子里的重量是:0苹果,83个梨和17个橙子等于篮子值217.

第二天,水果和篮子的价值发生了变化.To(apple = 2,Pear 3,Oranges 5),篮子值为348.当我假设体重超过(0,83,17)时,我得到的总值为334 - 不正确!通过我的脚本运行这个,我看到最接近的匹配是0苹果,76个梨,24个橙子,虽然它们等于348,当它的因素变化百分比是38%变化所以它是不可能的!

我知道我可以完全暴力,但如果我有1000个水果,它将无法扩展.不要跳过任何潮流,但像神经网络这样的东西可以迅速排除不太可能,所以我计算大量的数据？我认为他们必须比纯暴力更具可扩展性/更快速的方式？或者是否有任何其他类型的解决方案可以获得结果？

这是原始数据(记住程序只能看到价格和总篮数值):

这里有一些暴力代码(谢谢@paul Hankin比我的更清洁的例子):

def possibilities(value, prices):
    for i in range(0, value+1, prices[0]):
        for j in range(0, value+1-i, prices[1]):
            k = value - i - j
            if k % prices[2] == 0:
                yield i//prices[0], j//prices[1], k//prices[2]

def merge_totals(last, this, r):
    ok = []
    for t in this:
        for l in last:
            f …

我正在制作一款游戏有问题.我想我知道解决方案(或者应用什么解决方案),但不确定所有"碎片"是如何组合在一起的.

游戏如何运作:

(从如何处理数字猜谜游戏(带扭曲)算法？)

将为用户提供具有值的项目(值每天更改,并且程序知道价格的变化).例如

Apple = 1
Pears = 2
Oranges  = 3

然后他们将有机会选择他们喜欢的任何组合(即100个苹果,20个梨和1个橙子).计算机获得的唯一输出是总值(在此示例中,其当前为143美元).电脑会试着猜猜他们有什么.显然,第一回合无法正确使用.

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

下一轮用户可以修改他们的数量但不超过总数量的5%(或者我们可能选择的其他百分比.例如,我将使用5%).水果价格可以随意变化,因此总价值也可能因此而变化(为简单起见,本例中我没有改变水果价格).使用上面的例子,在游戏的第2天,用户在第3天返回$ 152和$ 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%的准确度,所以用户将永远进入它.

到目前为止我做了什么:

我已经采用了水果篮的所有价值和水果篮的总价值,并创造了一个包含所有可能性的大表.一旦我列出了所有可能性,我就使用了图论并为每个可能的解决方案创建了节点.然后,如果它在5%的变化范围内,我会在每天的节点之间创建边(链接)(例如day1到day2).然后我删除所有没有边缘的节点(链接到其他节点),并且当用户继续播放时,我也会在路径变为死路时删除整个路径.这很好,因为它缩小了选择范围,但现在我被卡住了,因为我想缩小这些选择范围.我被告知这是一个隐藏的马尔可夫问题,但是一个棘手的版本,因为状态正在改变(正如你可以看到上面的每个回合都添加了新节点,旧的/不可能的节点被删除).

**如果它有帮助,我在baum-welch模型(用于训练数据)的python实现上得到了一个惊人的答案(带有示例代码):Baum-Welch的实现示例**

我认为需要做什么(这可能是错的):

现在我缩小了结果范围,我基本上试图让程序尝试根据缩小的结果基础来预测正确的结果.我认为这是不可能的,但有几个人建议这可以通过隐藏的马尔可夫模型来解决.我想我可以对数据进行多次迭代(使用Baum-Welch模型),直到概率稳定(并且应该从用户获得更多转弯时变得更好).隐藏马尔可夫模型的方式能够检查拼写或手写并在出错时进行改进(在这种情况下的错误是选择在下一回合被删除的篮子是不可能的).

两个问题:

1. 如果所有状态首先相等,我如何计算过渡和发射矩阵？例如,由于所有州都同样可能必须使用某些东西来专门改变状态的概率.我正在考虑使用我所做的图来对具有最大边数的节点进行加权,作为过渡/发射状态计算的一部分？这有意义还是有更好的方法？

2. 如何跟踪各州的所有变化？随着新的篮子被添加并且旧的篮子被移除,存在跟踪篮子的问题.我虽然一个Hierarchical Dirichlet过程隐藏马尔可夫模型(hdp-hmm)将是我需要的但不完全确定如何应用它.

(对不起,如果我听起来有点沮丧..有点难以知道问题是可解决的但是无法在概念上掌握需要做的事情).

一如既往,感谢您的时间,任何意见/建议将不胜感激.

我正在寻找一种方法来确定是否存在方程的解,例如: 3n1 + 4n2 + 5n3 = 456,其中n1,n2,n3是正整数.

或者更一般:是零或正整数n1,n2,n3 ......解决方程k1n1 + k2n2 + k3n3 ... = m其中k1,k2,k3 ......和m是已知的正整数.

我不需要找到解决方案 - 只是为了确定是否存在解决方案.

编辑:

关于这个算法的实际使用:

在通信库中,我想在处理消息之前根据其大小决定给定消息是否有效.例如:我知道消息包含零个或多个3字节元素,零个或多个4字节元素和零个或多个5个字节元素.我收到了456字节的消息,我想在进一步检查其内容之前确定其有效性.当然,消息的标题包含每种类型的元素数量,但我想通过传递类似的东西在通信库级别进行第一次检查pair<MsgType,vector<3,4,5>>.