算法：在有m张赢牌和n张输牌的纸牌游戏中实现利润最大化

Question

假设一个赌场（C）有一个只涉及一个玩家和一个庄家的游戏。这个游戏是用m n张牌玩的，m张牌被标记为赢牌，n张牌被标记为输牌。

游戏规则/信息：

>

玩家知道每个阶段的获胜牌“m”和输牌“n”的数量。

玩家开始玩“X”数量，直到所有牌都抽出。

庄家非常非常聪明，有权根据玩家在牌桌上的赌注抽取一张获胜的牌或一张失败的牌。

每次抽奖都会减少任何一个类别的牌的数量，即如果抽到中奖牌，则中奖牌的数量变为“m-1”，反之亦然。

玩家也可以下注“0”金额。

如果玩家下注“W”金额并抽出一张获胜的牌。玩家获得2W作为回报，否则他失去了下注的金额

问题：推导出玩家应该遵循的算法或策略，以实现利润最大化。

一些例子：

测试用例-1：

Lets say m=0, n=1

玩家知道庄家没有机会让他输掉他下注的任何东西，所以他下注' 0 '金额。因此，他能做的最大值是x。

测试用例 - 2：

m=1, n=0

玩家知道庄家别无选择，只能抽唯一的牌，也就是赢的牌，所以他下注一切，也就是“X”，然后得到“2X”。所以，他以2X的金额退出赌场。

测试用例-3：

m=1, n=1 : 

假设玩家下注“W”金额 - 假设经销商抽取获胜卡：所以净金额= X W和m-

玩家将选择“W”以最大化其利润，只有当2（X-W）=X W时才能这样做=

因此，在这种情况下，玩家可以退出的最大数量= 4X/3

Answer 1

这是F#的解决方案。

建议：除非有必要，否则不要进行符号编程。在这种情况下，我们假设 X = 1

let stake = Array2D.zeroCreate 100 100
let bankroll =  Array2D.zeroCreate 100 100

for i in 1 .. 99 do
    stake.[0, i] <- 0.0
    bankroll.[0, i] <- 1.0

for i in 1 .. 99 do
    stake.[i, 0] <- 1.0
    bankroll.[i, 0] <- 2.0

stake.[0, 0] <- 0.0
bankroll.[0, 0] <- 1.0

let rec solve i j =
    if bankroll.[i, j] <> 0.0 then (stake.[i, j], bankroll.[i, j])
    else
       let a = snd (solve (i - 1) j)
       let b = snd (solve i (j - 1))
       let x = (b - a) / (a + b)  // solve (1 + x)a = (1 - x)b
       let y = (x + 1.0) * a
       stake.[i, j] <- x
       bankroll.[i, j] <- y
       (x, y)

solve 10 10 // = (0.06182352702, 1.333333333)

似乎只要赢牌的数量等于输牌的数量，玩家可以获得的最大利润总是4X/3