作者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/cn.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