作者s4300026 (s4300026)
看板Prob_Solve
標題[問題] 想問一個與這個問題相同的題目
時間Thu May 7 10:38:50 2020
小弟遇到一個問題如下，但我覺得應該有現成的題目與解答，我想問版友有沒有遇到相同
的題目，這樣個人比較容易找方法。
題目如下：
輸入兩列數字，第一列有兩個數字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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1588819132.A.92B.html
1F：推 LPH66: 這叫 Partition Problem 分堆問題, 它是 NP 完全 05/07 15:04
2F：→ LPH66: 但有偽多項式做法 (ie. 數字總和的多項式時間) 05/07 15:05
3F：→ LPH66: 咦等等我錯了, 這是 k-partition problem 05/07 15:07
4F：→ LPH66: 這個沒有偽多項式做法... 05/07 15:07
6F：推 ddavid: 樓上，這問題跟k-partition好像也不是全等的 05/07 16:56
7F：→ ddavid: 1.要求相等的目標是平均相等而非總和相等，這表示每一堆的 05/07 16:57
8F：→ ddavid: 大小不能直接用sum/k來預估 05/07 16:57
9F：→ ddavid: 2.目標是求出「最多可以分幾組」而不是給定k分k組 05/07 16:58
10F：推 ddavid: 直覺上解法是把所有數全部減去平均值成為一組新數列，然後 05/07 17:09
11F：→ ddavid: 不斷從這組新數列中取出加總為0且個數盡可能少的數就成為 05/07 17:10
12F：→ ddavid: 平均會符合條件的一組，看能夠取出幾組。 05/07 17:11
13F：→ ddavid: 例：3 2 4 1 5 3 -> 0 -1 1 -2 2 0 05/07 17:12
14F：→ ddavid: 兩個0可以直接獨立成為兩組，剩下1 -1，2 -2各一組，對應 05/07 17:13
15F：→ ddavid: 回去就是3 24 15 3共四組 05/07 17:13
16F：→ ddavid: 那問題就變成某種zero-sum problem了吧？ 05/07 17:19
17F：推 ddavid: 講錯了，應該是Subset sum problem 05/07 17:26
18F：推 LPH66: 每組個數是給定且大家都一樣的 n 個 05/07 21:36
19F：→ LPH66: 所以要求平均跟要求總和是一回事 05/07 21:36
20F：推 ddavid: 啊，對耶，我瞎了沒注意n XD 05/07 21:37
21F：→ ddavid: 抱歉啊m(_ _)m 05/07 21:38
22F：→ s4300026: 感謝一樓，我會朝這個方向找的 05/08 07:12
23F：→ s4300026: 我看了一下 k-partition problem，然後她說這是NP問題， 05/08 08:30
24F：→ s4300026: 我再查了一下NP，我得到的結論是用暴力法，就是一個一 05/08 08:30
25F：→ s4300026: 個測試，對吧？ 05/08 08:30
27F：→ s4300026: %A8 05/08 08:35
28F：推 ddavid: 對了，其實這仍然不是k-partition problem，因為 05/08 10:35
29F：→ ddavid: 1.k-partition problem並沒有要求每一組的數字個數相同 05/08 10:35
30F：→ ddavid: 2.這問題並沒有保證所有數字會分完，只是說最多能找出幾組 05/08 10:36
31F：推 ddavid: 所以感覺可以反覆執行Subset sum problem的做法一次找一組 05/08 10:38
32F：→ ddavid: 出來，但是中間會需要解決一個問題，就是需要證明能有某種 05/08 10:41
33F：→ ddavid: 取組的順序不會導致如果有某一組取走特定某些數會導致整體 05/08 10:42
34F：→ ddavid: 組數變少 05/08 10:42
35F：→ ddavid: 因為n限制的原因，直觀上我覺得不會發生這個問題，但還是 05/08 10:43
36F：→ ddavid: 需要證明 05/08 10:44
37F：推 LPH66: 有要求吧? 我引的那一頁的 3-partition 就是分成每組三個 05/09 03:00
38F：→ LPH66: "..., can S be partitioned into m *triplets* S_1, ..." 05/09 03:01
39F：→ LPH66: 所以它確實不只要求組數是三分之一, 每組個數也要求是三個 05/09 03:01
40F：推 ddavid: 啊，確實如此，一錯再錯XD 05/10 12:08