算法：利用m張獲勝牌和n張丟牌，使紙牌遊戲的利潤最大化

假設一家賭場（C）擁有一個只涉及一名玩家和一名經銷商的遊戲。該遊戲使用m + n張牌，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'。所以，他以2倍的金額退出了賭場。

測試用例 - 3：

m=1, n=1 :

比方說玩家下注 'W' 量 - 比方說經銷商彩票獲獎卡：所以淨量= X + W和M-> 0和正> 1：因此，在這種情況下的最大數量X + W - 如果經銷商提取丟失卡：所以淨剩餘數= XW和m-> 1且n> 0：因此，此情況下的最大數量爲2（XW）

玩家將選擇'W'以使其利潤最大化，這僅在2（XW）= X + W => W = X/3的情況下才能完成。

因此，最大量玩家可以在這種情況下走出= 4X/3

來源

2012-12-15 Sunil

聽起來像動態編程給我。如果可以導出m = 1，n = 1，那麼做m = x，n = y的困難是什麼，因爲它只依賴於m = x-1，n = y或m = x，n = y-1只取決於更簡單的已知情況。 – colinfang

這是正確的，但並不那麼容易。當你坐下來開始爲它編寫代碼時，問題就出現了嗎？您將通過求解方程式在數學上進行計算，您可以通過編程方式計算該案例的難度。我可能不是一個很好的編碼器，但是我發現編碼很困難 – Sunil

這裏是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

來源

2012-12-16 13:28:02 colinfang

算法：利用m張獲勝牌和n張丟牌，使紙牌遊戲的利潤最大化

回答

相關問題