一道武器强化题

czw0323

不考虑辅助宝石的话，从+0到+18平均需要花费的RMB为：
   1*5*10*40*(1+0.95+0.95^2+0.95^3)*(1+0.65+0.65^2+0.65^3)*(1+0.3+0.3^2+0.3^3)*(1+0.2+0.2^2+0.2^3+0.2^4+0.2^5)/(0.95^4*0.65^4*0.3^4*0.2^6)

ans =

  4.0923e+011 就是4092.3亿元，真黑呀！！！

czw0323

不好意思搞错了，是相加的，答案应该是：
不考虑辅助宝石的话，从+0到+18平均需要花费的RMB为：
(1+0.95+0.95^2+0.95^3)/0.95^4+5*(1+0.65+0.65^2+0.65^3)/0.65^4+10*(1+0.3+0.3^2+0.3^3)/0.3^4+40*(1+0.2+0.2^2+0.2^3+0.2^4+0.2^5)/0.2^6

ans =

  7.8302e+005
也就是78万3020 元

好了开始思考最优方案了

piaofeiaaaa

czw0323: Re:一道武器强化题

首先,先考虑  0到+4级  到达+4,所消耗RMB最少是多少.很明显就可以看出用A类宝石最为合算.
     1、假设0到...

这个看楼主的意思是强化宝石只有一种，分不同阶段而已
10000是什么意思 呵呵 看看

feiye

我是这样考虑的，首先考虑成功率的关系，当成功率大于50%的时候，则必然可以升级。成功率低于50%的时候，由题设可知不成功归最低等级，消耗的石头将大大增加。所以可以确定最节约的方案为几率50%以上。升级石头的多少和成功率成反比关系。
1-4级因为性价比和概率的关系。连成4把的几率为95%^4=81.45%。因为只升级4级，当几率为81%的石头，升级5级才有1次失败。考虑最大值，那么消耗4个石头可以到4级。我们由此可知当连成4把的几率>=80%的时候，消耗石头最少。可以有这么个对比关系 4把连续成功80% 对应 4颗石头。后面要使用这个关系简化做题。
4-8级的概率为65%，通过题设可知必须要连成4把才能到8级。考虑到最少用多少石头，那么4次连成的成功率为65%^4=0.178 对应1-4级 80%的4把连成消耗最少石头。(0.8/0.178)*4=17.977 那么应该是 18个石头可以成功。单个宝石价值5块，那么18个石头为90元。由此可知，B和C宝石由于单价格过高，抛弃。
考虑A宝石 1个A宝石相当于2个强化石头。那对于一组强化4连成来说，就要消耗到6个石头。那就是说几率不变的情况下需要多消耗1.5倍的石头，但是几率的增加远远达不到平衡1.5倍的效果。所以不选择使用几率石。
8-12级的概率为30%，当几率低于50%的石头，我们知道消耗的石头要增加的更多。所以我们要增加强化的概率。要大于50%的成功率。因为最多只能放3个石头，一共考虑几种组合方式。
2A+B几率为50% 对应 70 +40
2B+A      55% 对应 110+40   
3B为      60% 对应 150+40
2B+C      65% 对应 200+40           性价比 2B+C>2C+A
2C+B      70% 对应 250+40
3C        75% 对应 300+40
当几率都计算到100%成功时，选用2A+B消耗最低为220元。所以选择2A+B
0.5^4=0.0625  (0.8/0.0625)*4=12.8 消耗13组石头，1组石头包括《4个强化C级石头+（2A+B）几率石头》
一共消耗的钱是13*220=2860元
我也计算了下3C情况下的价格是 3740元  证明推断是正确的。
12-18级不能用上面的计算，还没想好用哪种方式更好。






     

piaofeiaaaa

这问题还这么靠前啊，O(∩_∩)O~
我举个简单的例子，做个参考，最笨的办法呵呵，抛砖引高人
0-2级 宝石概率为40%，价钱为10，辅助宝石10%，价钱为10，失败归零。
那么按照问题，要想成功就要有连续的两次成功，那么连续两个的情况共有(0失败1成功)
A:00   B:01   C:10   D:11  四种
失败归零，决定如下说法
A,B情况 玩家只使用 [em2]一个石头，C使用 [em14]2个石头，D使用 [em14]2个石头且成功。
玩家使用辅助宝石情况有 同样四种
情况1.00
A:0.6*0.6=0.36   B:0.24    C:0.24    D:0.16
使用金钱：0.36/0.16*10+0.24/0.16*10+0.24/0.16*20+20=1400/16
情况2，3，4.。。。。。。 [em7]
不知道这个思路对不呵呵

piaofeiaaaa

当然 在第一次失败后 你是直接放弃下一个的 所以你可以设定概率为1，情况这样分类
第一次就失败，第二次失败，第二次成功，（当然最后一次失败与成功是可以连接的）算法为
（0.6*10+0.24*20+0.16*20）/0.16

荒原

从数学模型来看，这道题是典型的“随机控制问题”，或者说是“马尔可夫动态规划”(MDP)问题，但幸运的是，解答还算比较简单

这个问题，具有所谓的“最优子结构”，所以可以用“动态规划”的方法求解，可以参看鼎鼎有名的《算法导论》里第15章关于动态规划里的论述，那里的装配线调度问题和这里的问题实质上是神似的.

下面考虑都是平均花费

简单的说，就是为了从17级最经济的升到18级（记最经济的花费是V(17)），对于每种玩家的放宝石的策略，考虑17级升级时的两种可能，一种是直接升到18，另一种是降到12级，但我们只考虑从12级最经济升到18级的花费，记为V(12),那么根据著名的Bellman方程，有V(17)=min(f,f+q*V(12)),这里的最小值是玩家在17级时所有的放入辅助宝石策略空间里取的，f是该策略的总花费，q则是失败概率，这样的话，v(12),v(13),...,v(17)每个都可以写一个方程，它们组成一个6个未知数，6个方程的方程组，可以解出答案来，类似的可以一直算到V(11),v(10),...,v(0)

求解bellman方程，也有其他的数值方法，比如迭代不动点法

这类武器强化问题，其实是个马尔可夫链模型，直接根据转移矩阵P，可以算出从初始状态首次到达某状态的平均步数，我以前为我们自己游戏里的宝石加星算过每级所需的平均步数和平均耗费

piaofeiaaaa

楼上大哥 给你发了个邮件啊

荒原

嗯,我回了你的邮件了