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

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

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間13年前 (2011/02/27 10:56)推噓0(0推 0噓 0→)

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

我試著先改成以下的情況，複製了之前計算過的method。跑出的答案就是1600, choose: 1 2 3 4 不過我想可能要多生幾個case來測試，無法確認正確性。 Bleed for(int i = 0; i < n; ++i) { if(i > 0) { method[i] = method[i - 1]; } 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; } } } } Bleed == 我剛看懂意思了，的確有盲點。現在改一下程式碼，希望不要大改才好。 Bleed ※ 引述《AmosYang (Omoide wa Okkusenman!)》之銘言： : 我認為這解法的方向正確 (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) [[以下請忽略]] 我有點不太懂意思，但我稍微講解一下程式，因為我覺得以上這兩點在這個程式都有考慮到才是？一般來說，換零錢是求解法有幾種，所以只需要一維陣列。可是注意看，我的是一維的vector裡面再包set， set就是解的集合。所以第一點要先放入所有解的部分，在內for迴圈j >= coin[i]的等號成立，就相當於是每一組初解都會放進去，因為j == coin[i]的時候，j - coin[i] == 0，是會跑到method[0].size()，而一開始被我放入了虛擬的一個解0。第二點的部分，因為是set，而每個元素int就是以bit畫計選擇的號碼。對於method[1000]來說，如果兩組解是bit1 | bit2和bit2 | bit3，很明顯是int數值6和12，數值不同會被set視為不同解。而如果用recursive的話，可能會有重覆計算的效率問題， 400 2 1 3 600 2 2 4 500 2 1 2 500 2 3 4 我們只考慮以1000為下一個出發點的情況。因為我是用set，所以對於選擇1 2 3 4（分別是1 3 2 4和1 2 3 4）和金額1000（400 + 600和500 + 500），再以1000討論後續的可能時，我只會做一次。因為情況會變成bit1 | bit2 | bit3 | bit4這一組解而已，只做一次。這個程式實際上的做法和換零錢幾乎沒兩樣，因為我只是把解法全部記錄下來，加上不超過5個號碼的判斷並往後展開罷了。至於要如何運用其他的容器來寫這題，我可能要想一下。對於case 1000 2 3 4 200 2 1 2 400 2 2 3 跑出1000其實是正確的。因為原文作者設定是取5個號碼，而我在文中有說可能跑出最高金額但號碼不夠5個，要另外自行選擇無用的其他號碼湊滿5個。所以對於這個case的認知，我設計了一個case 1 -> 幾個test case（並非取幾組號碼） 3 -> 有幾個人簽樂透 1000 2 3 4 200 1 1 900 1 2 然後我把count_bit的魔術數字的<= 5改成<= 2，也就是我改成取2組號碼。跑出的結果就會是1100, choose：1 2。相當於900 + 200，會比1000來得大。 Bleed : ※ 引述《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: 114.43.113.80 ※ 編輯: bleed1979 來自: 114.43.113.80 (02/27 11:13) ※ 編輯: bleed1979 來自: 114.43.113.80 (02/27 11:23)