数列平均分配

aimisiyou

有一列数n1,n2,n3,n4……nk,均大于0，如何将这些数分成两组，使两组的和最接近？为了一般性，先将数列按从大到小的顺序排序。

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问题的应该不对吧。

yzj63298368

感谢提供！！！

zhystar

厉害！谢谢分享

tzfcn

算法不错，值得学习。

aimisiyou

反过来仔细想了下，稀里糊涂中原来使用的是动态规划方法
dp[i,j] =max{((if(dp[i,j-1]+n_j <=P),dp[i,j-1]+n_j,dp[i,j-1]),max(dp[i,j-1],dp[i+1,j]))}
    其中j > i
dp[i,j]表示从n_i到n_j中能取到与平均值P最接近的数值

aimisiyou

_$ (defun fen_2(lst)
  (setq sum (apply '+ lst))
  (setq p (/ sum 2))
  (setq lst (vl-sort (mapcar '(lambda (x) (* 1.0 x)) lst) '>))
  (setq lst1 (mapcar '(lambda (x y)   
                            (list
                                  (if (> (+ x y) p) x (+ x y))
                                   y   
                            )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
   (while (cdr lst1)
          (setq lst1 (mapcar '(lambda (x y)   
                                (list
                                  (if (> (+ (car x) (cadr y)) P)
                                                                         (max (car x) (car y))
                                                                                 (if (< (+ (car x) (cadr y)) (car y))
                                                                                     (car y)
                                             (+ (car x) (cadr y))
                                                                                  )
                                                                    )
                                                              (cadr y)
                                                            )
                              )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
   (car (car lst1))
)
FEN_2
_$ (fen_2 '(39 35 21 13 7 3))
59.0
_$ (fen_2 '(39 35 27 21 17 3))
69.0
_$

Michael527

楼主高人，算法高手            

aimisiyou

_$ (defun fen_2 (lst)
  (setq sum (apply '+ lst))
  (setq p (/ sum 2))
  (setq lst (vl-sort (mapcar '(lambda (x) (* 1.0 x)) lst) '>))
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (> (+ x y) p) x (+ x y))
                                  y   
                                 (if  (> (+ x y) p)
                                                                          (list x)
                                                                          (list  x y)
                                  )
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
  (while (cdr lst1)
       (setq lst1 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) p)
                                                              (if (>= (car x)  (car y))
                                                                       x
                                                                           y
                                                                  )
                                                                  (if (>= (+ (car x) (cadr y)) (car y))
                                                                       (list
                                                                                (+ (car x) (cadr y))
                                                                                (cadr y)
                                                                                        (cons (cadr y) (last x))
                                                                           )
                                                                           y
                                                                  )
                                                            )
                            )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
  (cons sum (cons (car (car lst1)) (cdr (cdr (car lst1)))))
)
(fen_2 '(39 35 27 21 17 3))
FEN_2
(142 69.0 (3.0 27.0 39.0))
_$ (fen_2 '(39 35 27 21 17 13 5 3))
(160 79.0 (17.0 35.0 27.0))
_$  (fen_2 '(39 35 27 27 25 25  23 21 17 3))
(242 121.0 (21.0 23.0 25.0 27.0 25.0))
_$ (fen_2 '(103 97 89 65 41 39 35 27 21 17 3))
(537 268.0 (3.0 65.0 103.0 97.0))
_$

aimisiyou

分三组的情况动态规划好像实现不了，没有头绪。但突然有个奇思妙想，感觉可以找到次优解。先整理下。

aimisiyou

深入研究后，发现此问题与一维下料问题直接挂钩，意想不到的收获！

aimisiyou

已经成功解决三分组（可以不等长），使得三组和值最接近。类推到N分组都没问题。可以找到所有最优解。
效率也很快，非全组合算法。

aimisiyou

aimisiyou 发表于 2019-11-7 01:18
_$ (defun fen_2 (lst)
  (setq sum (apply '+ lst))
  (setq p (/ sum 2))

这个算法有问题，运气不好时会得出错误答案。
如
_$ (fen_2 '(3.8 3.5 2.7 2.3 -1.6))
(10.7 3.4 (-1.6 2.7 2.3))

正确的分组是{3.5 2.3}   {3.8 2.7 -1.6}.
固定的顺序没有考虑有些间隔组合情况。