求数字列表平衡分配的算法

mahuan1279

用递归实现求P函数
_$ (defun fp(sum)
  (if (= sum (fix sum))
      (if (= (rem sum 3) 0)
        (setq va (/ sum 3))
                (setq va (+ (fix (/ sum 3)) 1))
           )
      (setq va (/ (fp (* 10 sum)) 10.0))
   )
)
FP
_$  (fp 12)
4
_$ (fp 1.5)
0.5
_$ (fp 14)
5
_$ (fp 1.76)
0.59
_$  (fp 17.80)
6.0
_$ (fp 17.81)
5.94
_$ (fp 17.82)
5.94

mahuan1279

怎么又碰上递归BUG

_$ (fp 1.767)
0.589
_$ (fp 1.768)
0.59
_$ (fp 1.769)
0.589667
1.769的结果应该是0.59

masterlong

麻烦mahuan1279讲解下前面算法的思路
等明后天交了图以后仔细琢磨一下

fp函数暂时没时间研究
凭感觉应该要先确定sum小数点的位数吧
最后的平均值再根据位数向上取整

mahuan1279

masterlong 发表于 2019-11-5 22:40
麻烦mahuan1279讲解下前面算法的思路
等明后天交了图以后仔细琢磨一下

20楼我已经写出算法了啊。根据不可靠经验，将从大到小的数依次放入，要么使第一组和值尽快到达P-nk(最后一步可以将nk放入第一组，使得和接近p),然后让第二组和值尽快到达P，最后让第三组的和值接近P，如果三组中都有数，那么就将ni放入和值最小的那组（保证三组尽量同步上升）。

mahuan1279

分两组的情况：
如图，从第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问题的应该不对吧。

mahuan1279

\(反过来仔细想了下，稀里糊涂中原来使用的是动态规划方法\\
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最接近的数值和\)

mahuan1279

_$ (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
_$

mahuan1279

_$ (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))
_$

xinxirong

组合法是最优解，不过以现在的计算能力是没法实际运行。第一种是贪心算法，速度最快得到次优解，但如果数据偏差太大，结果也是没法看。你这种需求还算简单，有时候分N组，每组的容量不等

mahuan1279

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