Re: [問題] 一堆數字取組合最大值
基於暴搜提兩個 heuristic 的想法
1. 在 (Xn, Yn) 和 (Xm, Ym) 之間作選擇的時候，
如果 Xn >= Xm 且 Yn >= Ym ，則應該選擇 (Xn, Yn) ， (Xm, Ym) 可不用考慮。
簡單的證明是，令現在已選擇的所有點之前項和為 a ，後項和為 b 。
則選擇 (Xn, Yn) 後的值為 (Xn + a) * (Yn + b) = XnYn + aYn + bXn + ab
而選擇 (Xm, Ym) 後的值為 (Xm + a) * (Ym + b) = XmYm + aYm + bXm + ab
因 Xn >= Xm 且 Yn >= Ym 故前者必 >= 後者。
反之，在 (Xn, Yn) 和 (Xm, Ym) 之間選擇要去除其一的時候，
如果 Xn >= Xm 且 Yn >= Ym ，則應該選擇 (Xm, Ym) ， (Xn, Yn) 可不用考慮。
這個 heuristic 無法處理的 worst case 就是上述條件式在任兩點間皆不成立。
(也就是類似所有的點都分佈呈現 pareto optimality 的樣子)
2. 這個問題的圖象化思考就是這些點都是二維向量，然後想要從中選出 k 個，
使得從原點出發以後將這些向量頭尾相連串起來所抵達的點，
其發向兩座標軸的垂直線及座標軸所圍出的矩形面積最大。
因此可以把題目反過來處理，也就是從把所有的向量全部串起後抵達的點，
挑出不選擇的 (n - k) 個向量，依這些向量的反方向走，最後抵達的點，
依上述方式圍出來的矩形面積要最大。
因此在暴搜的時候可以先任意移除 (n - k) 個向量並取得一組解，
則該解可作為圍出矩形面積的 lower bound ，如果有某個 DFS 走法，
移去特定數量的向量以後所抵達的點所圍出的面積已小於 lower bound ，
則可以不用繼續搜尋。透過 branch and bound 來去除不可能的解。
3. 我的直覺基本上也傾向這是一個 NP 問題，如果上述第一點的條件任兩點皆不成立，
亦即一開始 cismjmgoshr 推文所述的狀況，這種情況濾掉任何一個選擇，
似乎都無法避免落入 local optimal ，不過我沒力氣去想嚴謹的證明。
--
我實實在在的告訴你們，一粒麥子不落在地裡死了，
仍舊是一粒，若是死了，就結出許多子粒來。
約翰福音 12:24
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.24.61
→
10/06 04:07, , 1F
10/06 04:07, 1F
→
10/06 06:22, , 2F
10/06 06:22, 2F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 4 篇)：
問題
6
27