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

mahuan1279

masterlong 发表于 2019-11-5 11:17
这个算法估计还会有问题
因为很可能某一组求和=p时
最终的分组不是最优解

有时根据反例可以很好地来修改调整程序。但前提是找个反例也不容易。

mahuan1279

反例也很容易找到。
正确的分组应该是（100,92,10）（76，63，50，13），（71,45,33,20,15,9,6,3）每组和都是202

mahuan1279

正确的分法是（100,51,51,49,23）（99,98,23,22,18,15）（98,95,66,17）    和分别为274,275,276.
看样子是NP组合问题。

mahuan1279

对于分成两组，使其两组和值最接近，似乎有好的方法。

masterlong

不成熟的想法
先以mahuan1279兄的思路
完成初步的分组
在此基础上再互相交换

具体怎么做没想好
只采用填空式的方法
总会有考虑不周的地方

masterlong

这个事情主要是为了解决电气三相平衡的问题
填空式的方法
其实已经可以做到工程上实用的程度了
想做到完美
估计还有很长的路要走
交图在即
压住
不能让强迫症肆虐
感谢mahuan1279

mahuan1279

按照二分组的思路似乎有三分组的思路，我在完善下。

masterlong

(setq slist '(5.4 5.0 4.8 4.2 2.8 2.8 2.8 2.8 2.8 2.8))


(defun cfdx_div3()
(setq slist (vl-sort slist '>))
(setq 1biao (list (car slist))  1zh (car slist)
     2biao '()       2zh 0
     3biao '()       3zh 0
     4biao '()
)
(setq 3m (/ (apply '+ slist) 3.0))
(foreach x (cdr slist)
  (if (<= (+ 1zh x) 3m)
   (setq 1biao (cons x 1biao)
       1zh (+ 1zh x)
   )
   (if (<= (+ 2zh x) 3m)
    (setq 2biao (cons x 2biao)
        2zh (+ 2zh x)
    )
    (if (<= (+ 3zh x) 3m)
     (setq 3biao (cons x 3biao)
         3zh (+ 3zh x)
     )
     (setq 4biao (cons x 4biao))
    )
   )
  )
)
(foreach x 4biao
  (setq 99biao (list 1biao 2biao 3biao))
  (setq 99biao (vl-sort 99biao ''((a b) (< (apply '+ a) (apply '+ b)))))
  (setq 1biao (car   99biao)
      2biao (cadr  99biao)
      3biao (caddr 99biao)
  )
  (setq 1biao (cons x 1biao))
)
(setq 99biao (list (reverse 1biao) (reverse 2biao) (reverse 3biao)))
(setq 99biao (vl-sort 99biao ''((a b) (> (apply '+ a) (apply '+ b)))))
(princ 99biao)
(princ)
)

mahuan1279

(foreach x (cdr slist)……
这段程序跟我4楼和7楼的算法思路有些出入，你可以再看看。备注：当列表最小值比较大时，分得的三组的和可能相差较大。对于大部分都是小数据的列表，结果还能勉强凑合。

mahuan1279

将4楼和7楼思路整理了下，算法如下：
1、按从大到小排序，n1>n2>n3>n4>……nk，p=sum/3，三组分别为空，即{} {} {}
2、将n1分别放入第一组，即{n1},{},{}；
3、若n2+n1<=p-nk则将n2放入第一组，否则放入第二组；即两种情况{n1+n2},{},{}或{n1}、{n2}、{}
4、将n3依次放入三个组中，若该组和值+n3<=p-nk,则将n3放入第一个能满足要求的组中,跳出转至放n4;若三组均不能满足，将n3放入和值最小的组中；
5、n4类似n3放置规则
6、……直至放完nk,最后完成分配。

备注：当sum能被3除尽时，p=sum/3,如12/3=4,1.5/3=0.5
          当sum不能被3除尽时，p=sum/3向上取数,如14/3=5,1.76/3=0.59
好像求P的函数（对于有小数位的情况）有点坎坷啊。