PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

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