一開始用遞迴DFS, 結果最後一個測資TLE, 測資n=30, 值多在100~200, 求和4001, 没有太多情況可砍

求和問題相當於有2^n種情形(每個值可選可不選), 可看成是由0101組成的mask和值的array做sum_of_product

做法:

1. 值要先排序(python一行解決)
2. 值分成2半, 各有2^15種組合
3. 先把後半所有可能產生出來, 並且對某質數用餘數分類(hash)
4. 前半依序產生出來, 去找適合的後半組合, 因為有分類所以組合數可縮成1/K

一開始用遞迴DFS, 結果最後一個測資TLE, 測資n=30, 值多在100~200, 求和4001, 没有太多情況可砍

求和問題相當於有2^n種情形(每個值可選可不選), 可看成是由0101組成的mask和值的array做sum_of_product

做法:

1. 值要先排序(python一行解決)
2. 值分成2半, 各有2^15種組合
3. 先把後半所有可能產生出來, 並且對某質數用餘數分類(hash)
4. 前半依序產生出來, 去找適合的後半組合, 因為有分類所以組合數可縮成1/K

懂了,但output卻不是完全的按照順序,是有什麼細節漏掉嗎,大大求解QAQ

我的輸出如下 (來自範例) :                                                                                                                            5 15 80, 5 10 15 70, 5 15 20 60, 5 15 30 50, 5 10 15 20 50, 5 10 15 30 40, 10 40 50, 10 20 70, 10 30 60, 10 20 30 40, 20 80, 20 30 50, 30 70, 40 60

銘芬這個報告寫得很棒，也很白話。

如果看不懂，就是練習還不夠。

寫信問我的朋友，可以附上 ideone 程式碼討論。

一開始用遞迴DFS, 結果最後一個測資TLE, 測資n=30, 值多在100~200, 求和4001, 没有太多情況可砍

求和問題相當於有2^n種情形(每個值可選可不選), 可看成是由0101組成的mask和值的array做sum_of_product

做法:

1. 值要先排序(python一行解決)
2. 值分成2半, 各有2^15種組合
3. 先把後半所有可能產生出來, 並且對某質數用餘數分類(hash)
4. 前半依序產生出來, 去找適合的後半組合, 因為有分類所以組合數可縮成1/K

我1.5s過了，太感謝了^^