两数组通过转移、交换数据使得差值最接近固定数值
已知两数组均按降序排列，如S1=，S2=,如何通过转移（一个数据从一组移到另一组）、交换（两不同组中的数据一对一交换），使得两组和的差值最接近已知数K=17（可正、负偏离，偏离越小越好）？
补充内容 (2019-11-13 07:13):
数组元素都为正数。 说白了，就是将一组数据，取一部分出来，使之总和尽可能接近某个确定值 gxqcn 发表于 2019-11-12 14:54
说白了，就是将一组数据，取一部分出来，使之总和尽可能接近某个确定值
嗯，组合问题，有什么好算法么？ 就是背包问题。 zeroieme 发表于 2019-11-12 15:47
就是背包问题。
理解中的背包算法是首先挑选价值最大的物品，使得物品容量不超过背包容量，物品价值总额最大。这个问题怎么具体运用背包算法？ 本帖最后由 王守恩 于 2019-11-13 07:16 编辑
我只能做具体的题目。
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
王守恩 发表于 2019-11-12 19:23
我只能做具体的题目。
1，6个数+9个数=15个数的和=100+92+76+71+63+50+45+33+20+15+13+10+9+6+4=607
2， ...
你只考虑进行交换操作吗？还可以进行转移操作啊，比如结果一组是7个数，一组是8个数的情况呢？ aimisiyou 发表于 2019-11-12 19:49
你只考虑进行交换操作吗？还可以进行转移操作啊，比如结果一组是7个数，一组是8个数的情况呢？
题目看懂了：在15个数里，选若干个数，使 “和” 尽可能向295靠拢。 这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小
问题是……没记错，对给定集合，判断其是否存在子集使得子集中全体元素等于0，是一个NPC问题
也就是说题目妥妥的是NP-hard
大概率应该还是NPC不过没区别
反正搜就是了
多项式算法不存在的
本帖最后由 aimisiyou 于 2019-11-12 23:32 编辑
.·.·. 发表于 2019-11-12 23:21
这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小
根据我的算法能很快的找到一组较好解。
当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)
(listx 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)
(listx 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))