这问题我也想了很久 (自从看到题目之後到现在也二个星期了) 想到一个方法在本文最下面，有待各位先进帮忙看有没有问题 (小弟没学过演算法，所以请多指教..) 想先请教有没有可能有这种情况发生？ 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)