作者chubiei (:))
站內Prob_Solve
標題Re: [問題] 樂透號碼最佳化的問題
時間Wed Jan 12 13:54:03 2011
※ 引述《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
1F：推 shipship:抱歉我看不懂a)將對獎資料轉換為array[i][20]是甚麼意思? 01/12 21:54
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)
2F：推 seanwu:嗯....你想說的是 sum[j] += arra[i][j] ? 01/12 23:04
3F：→ seanwu:關於... "要給哪五個號碼號碼才能對中最多筆" 01/12 23:07
4F：→ seanwu:下面那段演算法不是只是統計出現最多次的數字是哪"一"個嗎? 01/12 23:08
5F：推 seanwu:噢還有... 從 1. 中 "設weight為1" 來看... 01/12 23:11
6F：→ seanwu:所有物品的重量都是1? 那這樣的背包問題不能做嗎... 01/12 23:12
7F：→ shipship:我怎麼感覺你是在統計哪個數字出現最多次? 01/13 11:29
8F：推 ledia:這樣沒有解到 knapsack problem 啊 01/13 11:40
9F：→ gozule:給樓上，這是類似NPC證明中的reduce而已，並不是在解問題 01/18 22:29
10F：推 seanwu:reduce的方向...好像不太對? 01/19 04:10
11F：推 seanwu:舉個很爛的例子好了，我現在的問題是: 找n個數字中的最大值 01/19 04:13
12F：→ seanwu:那我設n個物品，weight皆為1，value為原數字的值 01/19 04:14
13F：→ seanwu:至於背包的總重限制，我設為1 01/19 04:15
14F：→ seanwu:所以我把找最大值這件事，reduce成knapsack problem了 01/19 04:16
15F：→ seanwu:所以找最大值很難，目前我們沒有多項式時間的做法 01/19 04:16
16F：→ ledia:我當然知道是 reduce, 但是 reduce 也要解得到那個問題啊 XD 01/19 14:55