PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者AmosYang (Omoide wa Okkusenman!)時間13年前 (2011/02/27 09:49)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串6/9 (看更多)

我認為這解法的方向正確 (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)