[問題] 想問一個與這個問題相同的題目

[s4300026 (s4300026)]

小弟遇到一個問題如下，但我覺得應該有現成的題目與解答，我想問版友有沒有遇到相同
的題目，這樣個人比較容易找方法。

題目如下：
輸入兩列數字，第一列有兩個數字m、n，m代表第二列要輸入的數字個數，n代表希望把第
二列的數字每n個分成一組，限制條件為每組的平均值要與第二列的總平均相符。

求最大可分成的組數與組合

舉例

輸入
6 2
1 2 3 4 5 6

輸出
3
1 6
2 5
3 4

理由
第二列的數字總和平均值為3.5
因此輸出的每列的平均值也要是3.5

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.242.160 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1588819132.A.92B.html
推 LPH66: 這叫 Partition Problem 分堆問題, 它是 NP 完全
→ LPH66: 但有偽多項式做法 (ie. 數字總和的多項式時間)
→ LPH66: 咦等等我錯了, 這是 k-partition problem
→ LPH66: 這個沒有偽多項式做法...
→ LPH66: https://en.wikipedia.org/wiki/3-partition_problem
推 ddavid: 樓上，這問題跟k-partition好像也不是全等的
→ ddavid: 1.要求相等的目標是平均相等而非總和相等，這表示每一堆的
→ ddavid: 大小不能直接用sum/k來預估
→ ddavid: 2.目標是求出「最多可以分幾組」而不是給定k分k組
推 ddavid: 直覺上解法是把所有數全部減去平均值成為一組新數列，然後
→ ddavid: 不斷從這組新數列中取出加總為0且個數盡可能少的數就成為
→ ddavid: 平均會符合條件的一組，看能夠取出幾組。
→ ddavid: 例：3 2 4 1 5 3 -> 0 -1 1 -2 2 0
→ ddavid: 兩個0可以直接獨立成為兩組，剩下1 -1，2 -2各一組，對應
→ ddavid: 回去就是3 24 15 3共四組
→ ddavid: 那問題就變成某種zero-sum problem了吧？
推 ddavid: 講錯了，應該是Subset sum problem
推 LPH66: 每組個數是給定且大家都一樣的 n 個
→ LPH66: 所以要求平均跟要求總和是一回事
推 ddavid: 啊，對耶，我瞎了沒注意n XD
→ ddavid: 抱歉啊m(_ _)m
→ s4300026: 感謝一樓，我會朝這個方向找的
→ s4300026: 我看了一下 k-partition problem，然後她說這是NP問題，
→ s4300026: 我再查了一下NP，我得到的結論是用暴力法，就是一個一
→ s4300026: 個測試，對吧？
→ s4300026: https://zh.m.wikipedia.org/zh-hant/NP%E5%AE%8C%E5%85
→ s4300026: %A8
推 ddavid: 對了，其實這仍然不是k-partition problem，因為
→ ddavid: 1.k-partition problem並沒有要求每一組的數字個數相同
→ ddavid: 2.這問題並沒有保證所有數字會分完，只是說最多能找出幾組
推 ddavid: 所以感覺可以反覆執行Subset sum problem的做法一次找一組
→ ddavid: 出來，但是中間會需要解決一個問題，就是需要證明能有某種
→ ddavid: 取組的順序不會導致如果有某一組取走特定某些數會導致整體
→ ddavid: 組數變少
→ ddavid: 因為n限制的原因，直觀上我覺得不會發生這個問題，但還是
→ ddavid: 需要證明
推 LPH66: 有要求吧? 我引的那一頁的 3-partition 就是分成每組三個
→ LPH66: "..., can S be partitioned into m *triplets* S_1, ..."
→ LPH66: 所以它確實不只要求組數是三分之一, 每組個數也要求是三個
推 ddavid: 啊，確實如此，一錯再錯XD