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

[chubiei (:))]

※ 引述《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
推 shipship:抱歉我看不懂a)將對獎資料轉換為array[i][20]是甚麼意思?
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)
推 seanwu:嗯....你想說的是 sum[j] += arra[i][j] ?
→ seanwu:關於... "要給哪五個號碼號碼才能對中最多筆"
→ seanwu:下面那段演算法不是只是統計出現最多次的數字是哪"一"個嗎?
推 seanwu:噢還有... 從 1. 中 "設weight為1" 來看...
→ seanwu:所有物品的重量都是1? 那這樣的背包問題不能做嗎...
→ shipship:我怎麼感覺你是在統計哪個數字出現最多次?
推 ledia:這樣沒有解到 knapsack problem 啊
→ gozule:給樓上，這是類似NPC證明中的reduce而已，並不是在解問題
推 seanwu:reduce的方向...好像不太對?
推 seanwu:舉個很爛的例子好了，我現在的問題是: 找n個數字中的最大值
→ seanwu:那我設n個物品，weight皆為1，value為原數字的值
→ seanwu:至於背包的總重限制，我設為1
→ seanwu:所以我把找最大值這件事，reduce成knapsack problem了
→ seanwu:所以找最大值很難，目前我們沒有多項式時間的做法
→ ledia:我當然知道是 reduce, 但是 reduce 也要解得到那個問題啊 XD