Re: [問題] 樂透號碼最佳化的問題
看板Prob_Solve (計算數學 Problem Solving)作者chubiei (:))時間14年前 (2011/01/12 13:54)推噓6(6推 0噓 10→)留言16則, 4人參與討論串3/9 (看更多)
※ 引述《shipship (Ship)》之銘言：
: 最近在跑一個模擬，遇到一個最佳化問題請各位板大幫忙看看:
: 現有一個對獎系統，從20個號碼中選5個做為這次的中獎號碼
: 有一群下注資料，格式如下：
: 978 3 2 10 13 //獎金978元，買了三個號碼，分別為2,10,13
: 5921 2 1 14
: 8027 4 1 4 6 9
: 7931 4 5 9 10 15 //獎金7931元，買了四個號碼，分別為5,9,10,15
: 4957 2 2 16
: 中獎的條件是該客人所買的號碼全中(全部都在5個中獎號碼中出現)
: 假設今日開獎號碼為1 2 4 10 13 16
: 則總獎金為978+4957
: 請求出，開出哪5個號碼，可以使得大家所得到的獎金最高？
: 每個人可以買的號碼數量為2~5，資料筆數不超過六千
: 我想了好久，目前都出的演算法，分析一下都還是暴力解。
: 請板大有甚麼意見請踴躍討論 感謝
這個問題是NP, 可以很簡單的轉換為knapsack problem:
1. 對每一筆資料data[i]轉換為knapsack的物品,
value就是獎金金額, 設weight為1
2. 對每一筆資料data[i], 將其對獎方式轉換為bitmask或array(參考上一篇)
那麼我們可以用很簡單的演算法算出, 要給哪五個號碼號碼才能對中最多筆
演算法如下:
a) for i <= n
do 將data[i]的對獎號碼轉換為array[i][20]
b) for j = 1, j <= 20
do for i = 1, i <= n
do sum[i] += arra[i][j]
c) 最大的sum[i]即為中最多次的號碼
3. 回到knapsack problem, 因為不可能對中比最大的sum[i]還多次,
我們設knapsack problem中能帶走物品的總重為W = max{sum[i]}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.14.188
推
01/12 21:54, , 1F
01/12 21:54, 1F
data[1] 1 4 15 -> array[1] 10010000000000100000
data[2] 10 12 19 -> array[2] 00000000010100000010
data[3] 3 7 11 19 -> array[3] 00100010001000000010
+ -----------------------
sum 10110010011100100020
^ max = sum[19]
※ 編輯: chubiei 來自: 111.83.24.144 (01/12 22:18)
※ 編輯: chubiei 來自: 111.83.24.144 (01/12 22:20)
推
01/12 23:04, , 2F
01/12 23:04, 2F
→
01/12 23:07, , 3F
01/12 23:07, 3F
→
01/12 23:08, , 4F
01/12 23:08, 4F
推
01/12 23:11, , 5F
01/12 23:11, 5F
→
01/12 23:12, , 6F
01/12 23:12, 6F
→
01/13 11:29, , 7F
01/13 11:29, 7F
推
01/13 11:40, , 8F
01/13 11:40, 8F
→
01/18 22:29, , 9F
01/18 22:29, 9F
推
01/19 04:10, , 10F
01/19 04:10, 10F
推
01/19 04:13, , 11F
01/19 04:13, 11F
→
01/19 04:14, , 12F
01/19 04:14, 12F
→
01/19 04:15, , 13F
01/19 04:15, 13F
→
01/19 04:16, , 14F
01/19 04:16, 14F
→
01/19 04:16, , 15F
01/19 04:16, 15F
→
01/19 14:55, , 16F
01/19 14:55, 16F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
