两数组通过转移、交换数据使得差值最接近固定数值

_only

已知两数组均按降序排列，如S1=[100, 92, 76 ,63 ,50 ,10]，S2=[71,45 ,33 ,20 ,15 ,13 ,9,6,4],
如何通过转移（一个数据从一组移到另一组）、交换（两不同组中的数据一对一交换），使得两组和的差值最接近已知数K=17（可正、负偏离，偏离越小越好）？

补充内容 (2019-11-13 07:13):
数组元素都为正数。

obibohazek

说白了，就是将一组数据，取一部分出来，使之总和尽可能接近某个确定值

ojaupobcisi

嗯，组合问题，有什么好算法么？

DJWilliamstada

就是背包问题。

渐行渐远

理解中的背包算法是首先挑选价值最大的物品，使得物品容量不超过背包容量，物品价值总额最大。这个问题怎么具体运用背包算法？

ohelorukozaxe

我只能做具体的题目。
1，15个数的和=100+92+76+71+63+50+45+33+20+15+13+10+9+6+4=607
2，较小一组的和应该是(607-K)/2=(607-17)/2=295，较大一组的和应该是607-295=312
3，按以下顺序求解
第一轮：295=4个数=5个数=6个数=7个数，312=4个数=5个数=6个数=7个数
第二轮：294或296=4个数=5个数=6个数=7个数，311或313=4个数=5个数=6个数=7个数
第三轮：293或297=4个数=5个数=6个数=7个数，310或314=4个数=5个数=6个数=7个数
第四轮：292或298=4个数=5个数=6个数=7个数，309或315=4个数=5个数=6个数=7个数
第五轮：291或299=4个数=5个数=6个数=7个数，308或316=4个数=5个数=6个数=7个数
4，具体操作：
100+92+76+9+6+4=287=295-8
100+92+76+9+6+(4+9)
100+92+76+13+9+6=296=295+1
100+92+(76-5)+13+9+(6+4)
100+92+71+13+9+10=295
方法不止一个，譬如：
92+76+50+45+20+13=296=295+1
(92+8)+76+50+45+20+(13-9)=295

inabilezami

你只考虑进行交换操作吗？还可以进行转移操作啊，比如结果一组是7个数，一组是8个数的情况呢？

isotaztiqotew

题目看懂了：在15个数里，选若干个数，使 “和” 尽可能向295靠拢。

uzmetub

这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小

问题是……没记错，对给定集合，判断其是否存在子集使得子集中全体元素等于0，是一个NPC问题
也就是说题目妥妥的是NP-hard
大概率应该还是NPC不过没区别
反正搜就是了
多项式算法不存在的

asomiajht

根据我的算法能很快的找到一组较好解。
当K=0时，不知能不能证明结果是最优解？
;;;程序中的k等于差值的一半
;;;如要将 '(100 92 76 63 57 50 10)和'(95 82 71 45 33 20 15 13 9 6 4)经过转移、交换数据使得两组差值接近17，则程序如下
;;;;(fen_2 (append '(100 92 76 63 57 50 10) '(95 82 71 45 33 20 15 13 9 6 4)) 8.5)
;;; (fen_2 (append '(100 92 76 63 57 50 10) '(95 82 71 45 33 20 15 13 9 6 4)) 8.5)
;;;(841 428 (13 20 33 45 50 57 63 76 71))
;;;
(defun fen_2 (lst k)
  (setq sum (apply '+ lst))
  (setq p1 (- (/ sum 2) k))
  (setq p2 (+ (/ sum 2) k))
  (setq lst (mapcar 'cadr(vl-sort (mapcar '(lambda (x) (cons (* x 1.0) (list x))) lst) '(lambda (ea eb) (>= (car ea) (car eb))))))
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (list (if (> (+ x y) p1) x (+ x y))
                                  y   
                                 (if  (> (+ x y) p1)
                                                                          (list x)
                                                                          (list  x y)
                                  )
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
    (setq lst2 (mapcar '(lambda (x y)   
                         (progn
                            (list (if (> (+ x y) p2) x (+ x y))
                                  y   
                                 (if  (> (+ x y) p2)
                                                                          (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)) p1)
                                                              (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)
                      )
            )
   )
  (while (cdr lst2)
       (setq lst2 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) p2)
                                                              (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 lst2)))
                           (cdr lst2)
                      )
            )
   )
  (if (<= (- sum (* 2 (cadr (car lst1))))
          (- (* 2 (cadr (car lst2))) sum)
          )
     (setq va (cons sum (cons (car (car lst1)) (cdr (cdr (car lst1))))))
     (setq va (cons sum (cons (car (car lst2)) (cdr (cdr (car lst2))))))
  )
  va
)

(FEN_2 '(5.12 3.62 3.02 3.92 3.32 3.12) 0)
(22.12 10.86 (3.32 3.92 3.62))

(FEN_2 '(6.32 5.12 3.62 3.02 3.92 3.32 3.12) 0)
(28.44 13.98 (3.12 3.32 3.92 3.62))

(FEN_2 '(7.58 6.32 5.12 3.62 3.02 3.92 3.32 3.12) 0)
(36.02 17.82 (3.92 7.58 6.32))

(FEN_2 '(29 7.58 6.32 5.12 3.62 3.02 3.92 3.32 3.12) 0)
(65.02 32.32 (3.32 29))