数列平均分配

aimisiyou

反过来仔细想了下，稀里糊涂中原来使用的是动态规划方法
\(dp[i,j] =\max{((\text{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 \gt 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 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))