找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 608|回复: 14

[原创] 数列平均分配

[复制链接]

已领礼包: 1857个

财富等级: 堆金积玉

发表于 2019-11-5 23:31:23 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
本帖最后由 aimisiyou 于 2019-11-12 09:38 编辑

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

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-6 00:07:05 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-6 08:53 编辑

如图,从第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问题的应该不对吧。
111.png
222.png
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 51个

财富等级: 招财进宝

发表于 2019-11-6 07:46:38 | 显示全部楼层
感谢提供!!!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

已领礼包: 960个

财富等级: 财运亨通

发表于 2019-11-6 08:15:13 | 显示全部楼层
厉害!谢谢分享
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2019-11-6 08:20:35 | 显示全部楼层
算法不错,值得学习。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-6 11:10:37 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-11 22:39 编辑

反过来仔细想了下,稀里糊涂中原来使用的是动态规划方法
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最接近的数值
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-6 13:57:42 | 显示全部楼层
_$ (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
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 6202个

财富等级: 富甲天下

发表于 2019-11-6 19:25:17 | 显示全部楼层
楼主高人,算法高手            
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-7 01:18:53 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-11 00:25 编辑

_$ (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))
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-7 08:41:37 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-7 08:45 编辑

分三组的情况动态规划好像实现不了,没有头绪。但突然有个奇思妙想,感觉可以找到次优解。先整理下。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 08:59:05 | 显示全部楼层
深入研究后,发现此问题与一维下料问题直接挂钩,意想不到的收获!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-10 19:38:25 | 显示全部楼层
已经成功解决三分组(可以不等长),使得三组和值最接近。类推到N分组都没问题。可以找到所有最优解。
效率也很快,非全组合算法。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-11 00:29:17 | 显示全部楼层
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}.
固定的顺序没有考虑有些间隔组合情况。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-28 20:02 , Processed in 0.214466 second(s), 57 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表