先把最重要的結論寫在最前頭， 那就是我並沒有想到什麼神奇的演算法 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 接續我的第二個解法。 在做擴充的時候，把原中獎金額加到擴充後的組合上， 這樣開出來的時候，就已經算好總共會中多少錢了。 複雜度還是只有 C(52,6)。 ※ 編輯: tkcn 來自: 140.114.78.231 (01/11 17:12)