PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 樂透號碼最佳化的問題

看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間14年前 (2011/01/11 15:18)推噓4(4推 0噓 3→)

留言7則, 3人參與討論串2/9 (看更多)

先把最重要的結論寫在最前頭，那就是我並沒有想到什麼神奇的演算法 XD 20 個號碼選 5 個開出，也就是共有 C(20,5) = 15504 個可能的開獎組合，這個數字實在說不上多，我想即使是暴力法應該也不會花太多時間。如果你只需要執行效率，而並不是非要提出一個演算法，我建議採用 bit mask 來處理這問題，例如開出 1 2 4 10 13 這五個號碼時，可以用 0001001000001011 (命名為 a) 來表示。購買 2,10,13 這三個號碼則是 0001001000000010 (命名為 b)，要判斷這 3 個號碼是不是全都包含在開獎號碼內，你只需要檢查 (~a & b)==0 即可。註: ~ 表示 bitwise not。我相信用這種寫法，比起陣列要快個五倍應該不是問題。另外就是可以消去 C(20,5) 中不可能出現的組合，(即沒有半個人中獎的組合) 我的想法是把所有的購買組合中只有一個號碼的先拿出來，重複的號碼也只取一個，然後加入另外一個數。例如數字 7 就會擴充成 (1,7), (2,7), ..., (6,7), (7,8), ..., (7,20) 然後再把所有購買組合種有兩個號碼的組合再加進去，一樣拿掉所有重複的，並且繼續重複至共有 5 個數字，這樣集合中任一個開獎組合，都可以保證至少有一個購買組合能中獎 (因為都是從購買組合擴充來的) 雖然這作法或許能加速，但並不會減少演算法的複雜度。 ※ 引述《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，資料筆數不超過六千 : 我想了好久，目前都出的演算法，分析一下都還是暴力解。 : 請板大有甚麼意見請踴躍討論感謝 -- ◤ ◥ ◢ ◣ T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！ ╰ ∕皿﹨ ◥皿◤ ╯ ◥█◤◢ ◥ ︶◤ Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.231

推

ledia

01/11 15:25, , 1^F

01/11 15:25, 1^F

推

shipship

01/11 16:46, , 2^F

01/11 16:46, 2^F

推

shipship

01/11 16:52, , 3^F

01/11 16:52, 3^F

→

shipship

01/11 16:53, , 4^F

01/11 16:53, 4^F

接續我的第二個解法。在做擴充的時候，把原中獎金額加到擴充後的組合上，這樣開出來的時候，就已經算好總共會中多少錢了。複雜度還是只有 C(52,6)。 ※ 編輯: tkcn 來自: 140.114.78.231 (01/11 17:12)