作者AmosYang (Omoide wa Okkusenman!)
看板Prob_Solve
标题Re: [问题] 乐透号码最佳化的问题
时间Sun Feb 27 09:49:04 2011
我认为这解法的方向正确 (orz 拜一下)，但直觉觉得程式写得有点小误差
1. 'method' 应该要先把所有已知的中奖组合先放进去
i = 0 to (n-1)
method[coin[i]].insert(coin_bit[i])
2. 光是跑一层 for-loop 来建表是不够的
例如: 假设有三组奖卷
1000 2 3 4
200 2 1 2
400 2 2 3
光跑一层 loop 最後只会求出中 $1000 这组解
是我的话这段会改写成 recursion 的型式 (dynamic programming)
至於记忆体的使用量…可以用 map/dictionary 这类的资料结构来代替 vector
(不过，够奸的输入资料还是可以让程式又炸效能又炸记忆体
还是直接开 array/vector 吧 XD)
※ 引述《bleed1979 (十三)》之铭言：
: vector< set<int> > method(sum + 1);
: method[0].insert(0);
: for(int i = 0; i < n; ++i) {
: for(int j = sum; j >= coin[i]; --j) {
: int k = j - coin[i];
: if(method[k].size()) {
: set<int> :: iterator it = method[k].begin();
: while(it != method[k].end()) {
: int new_int = *it | coin_bit[i];
: if(count_bit(new_int) <= 5) {
: method[j].insert(new_int);
: }
: ++it;
: }
: }
: }
: }
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 24.40.140.129
我想这不是新闻了，但我刚刚才发现到
上 google 查 recursion 这个字， google 会问: "Did you mean: recursion"
点下去後会回到同一页，google 会问: "Did you mean: recursion"
点下去後会回到同一页，google 会问: "Did you mean: recursion"
点下去後会回到同一页，google 会问: "Did you mean: recursion"
…
XD
※ 编辑: AmosYang 来自: 24.40.140.129 (02/27 09:56)
※ 编辑: AmosYang 来自: 24.40.140.129 (02/27 10:02)
更正: #2 “光是跑一层 for-loop 来建表是不够的”这句话得要撤回
这不代表跑一层 loop 就一定够，也不代表一定不够
只是单纯想通了之前原本支持 #2 的理论与其范例在数学上不应该存在…
※ 编辑: AmosYang 来自: 24.40.140.129 (02/27 11:59)