小弟遇到一个问题如下，但我觉得应该有现成的题目与解答，我想问版友有没有遇到相同
的题目，这样个人比较容易找方法。
题目如下：
输入两列数字，第一列有两个数字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