作者Hsiehshun (金毛獅王)
看板Math
標題[機統] 手遊抽箱問題
時間Wed Nov 4 16:03:21 2020
這是在某個手遊遇到的問題，情況如下
簡化版：
一個箱子內有 90 個物品，其中有 5 個「物品 B」
每次隨機自箱中取出一個物品，取後不放回
每抽結束後有兩種選擇
1. 繼續抽原本的箱子
2. 前進到下一個箱子，重新從 5 / 90 開始抽
問題：給定 N 抽 (N >> 90) 的情況下，找出最佳策略使得獲得「物品 B」的期望值最大
因為 N 夠大，我會覺得策略只和箱內剩餘數及剩下「物品 B」的個數有關，
直覺上我會認為最佳策略是當剩下「物品 B」比例小於 5/90 時就該重置，
但不知是否正確
實際版：
在 90 個物品中除了同樣有 5 個「物品 B」外，另外有 1 個「物品 G」
必須在「物品 G」已被抽出的情況下才可以選擇是否重置
同樣只考慮最大化「物品 B」
兩種情況我都沒有頭緒，想請教各位該如何解
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.189 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1604477003.A.E81.html
1F：→ hwanger : "直覺上我會認為最佳...">>>雖然沒有任何理論支持 11/06 16:55
2F：→ hwanger : 但我也覺得是可行的策略 不過如果沒有其他成本的 11/06 16:55
3F：→ hwanger : 考量 是不是直接抽到五個都出現 會比"期望"好? 11/06 16:55
4F：→ andrew43 : 我式子列不出來只好用模擬的。我試了6種策略和3種抽 11/11 00:18
5F：→ andrew43 : 奬次數，結果應該是「抽到5個奬馬上重置」的期望值 11/11 00:19
6F：→ andrew43 : 高且變異最小，而「一抽一重置」是最差策略。 11/11 00:20
8F：→ andrew43 : 每種實驗皆模擬10k次。 11/11 00:21
9F：→ andrew43 : 這結果同意hwanger的猜測 11/11 00:22
10F：→ hwanger : 謝謝測試 不知是否有測試原po所提的"當剩下「物品 B 11/11 06:51
11F：→ hwanger : 」比例小於 5/90 時就該重置"的策略 表現如何 畢竟 11/11 06:51
12F：→ hwanger : 有時每抽一次就會損失一些東西 感謝 11/11 06:51
13F：→ andrew43 : 尚無，有空再來做。若有則推文回應。 11/11 15:53
14F：→ hwanger : 謝謝 11/11 22:16
16F：→ hwanger : 喔喔 看起來比抽到五次再重置好 感謝 接下來就再想 11/12 16:23
17F：→ hwanger : 想如何解釋好了 11/12 16:23
18F：→ andrew43 : 我是寫了二隻遞迴函數去模擬，所以策略須固定。但 11/12 16:48
19F：→ andrew43 : 數學上怎麼做最佳化就不知道怎麼辦了，暴力解的複 11/12 16:48
20F：→ andrew43 : 雜度太高。 11/12 16:48
21F：推 xxxx9659 : 這題目好有趣！！ 11/13 22:20