小弟遇到一個問題如下，但我覺得應該有現成的題目與解答，我想問版友有沒有遇到相同
的題目，這樣個人比較容易找方法。
題目如下：
輸入兩列數字，第一列有兩個數字m、n，m代表第二列要輸入的數字個數，n代表希望把第
二列的數字每n個分成一組，限制條件為每組的平均值要與第二列的總平均相符。
求最大可分成的組數與組合
舉例
輸入
6 2
1 2 3 4 5 6
輸出
3
1 6
2 5
3 4
理由
第二列的數字總和平均值為3.5
因此輸出的每列的平均值也要是3.5

這叫 Partition Problem 分堆問題, 它是 NP 完全但有偽多項式做法 (ie. 數字總和的多項式時間)咦等等我錯了, 這是 k-partition problem這個沒有偽多項式做法...https://en.wikipedia.org/wiki/3-partition_problem

樓上，這問題跟k-partition好像也不是全等的1.要求相等的目標是平均相等而非總和相等，這表示每一堆的大小不能直接用sum/k來預估2.目標是求出「最多可以分幾組」而不是給定k分k組直覺上解法是把所有數全部減去平均值成為一組新數列，然後不斷從這組新數列中取出加總為0且個數盡可能少的數就成為平均會符合條件的一組，看能夠取出幾組。例：3 2 4 1 5 3 -> 0 -1 1 -2 2 0兩個0可以直接獨立成為兩組，剩下1 -1，2 -2各一組，對應回去就是3 24 15 3共四組那問題就變成某種zero-sum problem了吧？講錯了，應該是Subset sum problem

每組個數是給定且大家都一樣的 n 個所以要求平均跟要求總和是一回事

啊，對耶，我瞎了沒注意n XD抱歉啊m(_ _)m

感謝一樓，我會朝這個方向找的我看了一下 k-partition problem，然後她說這是NP問題，我再查了一下NP，我得到的結論是用暴力法，就是一個一個測試，對吧？https://zh.m.wikipedia.org/zh-hant/NP%E5%AE%8C%E5%85%A8

對了，其實這仍然不是k-partition problem，因為1.k-partition problem並沒有要求每一組的數字個數相同2.這問題並沒有保證所有數字會分完，只是說最多能找出幾組所以感覺可以反覆執行Subset sum problem的做法一次找一組出來，但是中間會需要解決一個問題，就是需要證明能有某種取組的順序不會導致如果有某一組取走特定某些數會導致整體組數變少因為n限制的原因，直觀上我覺得不會發生這個問題，但還是需要證明

有要求吧? 我引的那一頁的 3-partition 就是分成每組三個"..., can S be partitioned into m *triplets* S_1, ..."所以它確實不只要求組數是三分之一, 每組個數也要求是三個

啊，確實如此，一錯再錯XD