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

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

看板Prob_Solve (計算數學 Problem Solving)作者tropical72 (藍影)時間14年前 (2011/01/21 06:22)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/9 (看更多)

這問題我也想了很久 (自從看到題目之後到現在也二個星期了) 想到一個方法在本文最下面，有待各位先進幫忙看有沒有問題 (小弟沒學過演算法，所以請多指教..) 想先請教有沒有可能有這種情況發生？ 4568 元 | 1 號，2號，3號 1 元 | 1 號，2號，3號 1 元 | 1 號，2號，3號 1 元 | 1 號，2號，3號 ....... 如果有的話我想先進行併單會好些，就是開出 1, 2, 3 號的總金額併成同一張單。 (方便處理) 接下來是下面的問題... : 這個問題是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]} : 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] 這方法不知道和我之前的想法是不是一樣 - 都是錯的，這樣下來可能是全賠。 100 元 -> 1 2 200 元 -> 3 4 5 300 元 -> 3 11 6 400 元 -> 4 2 7 500 元 -> 6 7 8 -------------------------- 1號 => 100*1 = 100 2號 => 100*1 + 400*1 = 500 (3) 3號 => 200*1 + 300*1 = 500 (3) 4號 => 400*1 = 400 5號 => 200*1 = 200 6號 => 300*1 + 500*1 = 800 (2) 7號 => 400*1 + 500*1 = 900 (1) 8號 => 500*1 = 500 (3) 11號=> 300*1 於是選 2,3,6,7,8 號，結果只中一個 500 元，隨便 2 4 6 7 8, 3 6 7 8 11 都比較高另外如果選出來排第一名的就有 10 個，這也是件麻煩的事。 ---------------------------------------- 這裡先不考慮同組號碼問題同組的話先併成一張，如 1號 2號 3號有 200 張，總金額共 5000 元 (只是不知道合併的話會不會花更多時間) 100 元 -> 1 2 200 元 -> 3 4 300 元 -> 3 6 400 元 -> 4 7 500 元 -> 6 7 8 先從價格最高的開始挑, 500 元 -> 6 7 8, (500) + 400 元 -> 6 7 8,4, (900) + 300 元 -> 6 7 8,4,3 (1200) 五個數字全選完後，再去找有哪些中獎,total=1400 接著第一組號碼選過之後，丟到 array 裡面去，之後避免重覆計算 (我想這是個重要的動作，c++ 的話用 multimap 去紀錄這組號碼有哪幾筆資料在裡面) + 300 元 -> 6 7 8,4, (900) + 200 元 -> 6 7 8,4,3 ----> 和 array[0] 同一組，不去算了第一輪，包含 500 元最高的號碼是 6 7 8 4 3 第二輪裡面，要判斷 400 元，4 7 這二個號碼都包在 array[0] 裡面去了，所以不計第三輪裡面，要判斷 300 元，3 6 也包在 array[0]，不計第四輪，不計第五輪， 100 元，1 2 6 7 8，最高 600 元所以最佳號碼是 3 4 6 7 8 ------------------------------- 上面說明全都用 array 說明較為清楚，當然如一開始版友說的用 bitwise 去處理會快些。多建一個表，去避免多次運算，這方法有點像是質數的篩法再加上 traceback，不知道這樣會不會有暇疵，只是當張數一多的時候，可能用 20 組串遍去算會快些另外這個例子是假設已完成併單作業，不知道能不能加條件去判斷「如果目前選出的最佳號碼所獲得的金額已大於等於總賭注的一半時便可停止」以上面的例子而言，(100+200+...+500)/2 = 750，第一輪就已經算出 1400，這時候便可停下來。此外還需考慮另一種情形，便是該輪選出來的最佳號碼假設只有 1 2 3 三個號碼，這時在 array 裡面可記為 array[1] = {1,2,3,0,0} 接下來只要該彩票號碼是小於等於二個號碼的就不用去判斷它，因為這和 array[1] 裡面有二個可用號碼是矛盾的，甚至如果是 3,4,5 ，扣除掉那個 3 也是小於等於二個號碼，也不用去判斷。 -------------------------------- 以上說明有點長，懇請賜教 -- YouLoveMe() ? LetItBe() : LetMeFree(); -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.142 ※ 編輯: tropical72 來自: 180.177.76.142 (01/21 07:07)