作者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