我试着先改成以下的情况，复制了之前计算过的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)