数列平均分配

aimisiyou

有一列数n1>=n2>=n3>=n4……nk>0，如何将这些数分成两组，使两组的和最接近？

lsr314

背包问题 https://bbs.emath.ac.cn/thread-4042-1-1.html

aimisiyou

为什么不能上传图片？出现Server(IO)Error.

aimisiyou

lsr314 发表于 2019-11-6 09:14
背包问题 https://bbs.emath.ac.cn/thread-4042-1-1.html

背包问题得到的不一定是最优解吧。

aimisiyou

如图，从第2行起，设置每个节点结构为（sum,min,dis）sum表示目前能取到的最大和值（当然，有不大于平均值P的限制）
min表示目前的数列中的最小值
dis表示目前数列分成两组，两组和值的最小差值
可以找出节点之间的对应关系。
父节点pt（sum，min，dis）
两子节点p1（sum1,min1,dis1）、p2（sum2,min2,dis2）
min=min2
dis=max(dis1,dis2)-min(dis1,dis2)
sum=if(sum1+min2<=p,sum1+P,max(sum1,sum2))
根据最后的根节点再返回寻找其中一组数据（剩下的就为另一组数据）
若sum=sum1+min2,则该组数据由min2和节点1中的叶子节点中组成；
若sum=sum1，则该组数据由节点1中的叶子节点中组成；
若sum=sum2，则该组数据由节点2中的叶子节点中组成；
如图中根节点（59,3，0），返回寻找（红线）得3,21,35。
备注：程序目的是取得最接近平均值P的最大和值，dis定义有些问题（从第三行开始，仅仅表示目前存在差值为dis的两个分组，并不一定是差值最小的分组），但不影响最终结果sum最接近P。

本算法复杂度为O(n^2)，网上说这是NP问题的应该不对吧。

mathe

sum可以达到指数规模，比如$1,2,4,8,..,2^n$这n个数。

aimisiyou

mathe 发表于 2019-11-6 10:22
sum可以达到指数规模，比如$1,2,4,8,..,2^n$这n个数。

如果把大数加法运算看成常规加法运算，复杂度还是O（n^2）。

aimisiyou

再进一步，若是要分成三组，使其三组和值最接近（例如指标（sum1-p）^2+(sum2-p)^2+(sum3-p)^2最小），如何分组？

mathe

aimisiyou 发表于 2019-11-6 10:48
如果把大数加法运算看成常规加法运算，复杂度还是O（n^2）。

不对，这个算法是O(n*sum),但是在sum是n的指数时是指数时间复杂度的

aimisiyou

mathe 发表于 2019-11-6 10:51
不对，这个算法是O(n*sum),但是在sum是n的指数时是指数时间复杂度的

算法复杂度好像不考虑每个数据与规模n的关系吧？