数学研发论坛

 找回密码
 欢迎注册
查看: 399|回复: 24

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

[复制链接]
发表于 2019-11-12 13:32:50 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

补充内容 (2019-11-13 07:13):
数组元素都为正数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-12 14:54:40 | 显示全部楼层
说白了,就是将一组数据,取一部分出来,使之总和尽可能接近某个确定值
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-12 15:10:20 | 显示全部楼层
gxqcn 发表于 2019-11-12 14:54
说白了,就是将一组数据,取一部分出来,使之总和尽可能接近某个确定值

嗯,组合问题,有什么好算法么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-12 15:47:29 | 显示全部楼层
就是背包问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-12 16:04:10 | 显示全部楼层

理解中的背包算法是首先挑选价值最大的物品,使得物品容量不超过背包容量,物品价值总额最大。这个问题怎么具体运用背包算法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-12 19:23:32 | 显示全部楼层
本帖最后由 王守恩 于 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:49:53 | 显示全部楼层
王守恩 发表于 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个数的情况呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-12 20:07:11 | 显示全部楼层
aimisiyou 发表于 2019-11-12 19:49
你只考虑进行交换操作吗?还可以进行转移操作啊,比如结果一组是7个数,一组是8个数的情况呢?

题目看懂了:在15个数里,选若干个数,使 “和” 尽可能向295靠拢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-12 23:21:18 | 显示全部楼层
这不是NPC吗?
题目等价于找到一个给定集合的子集,子集里全体元素和与定值之差最小

问题是……没记错,对给定集合,判断其是否存在子集使得子集中全体元素等于0,是一个NPC问题
也就是说题目妥妥的是NP-hard
大概率应该还是NPC不过没区别
反正搜就是了
多项式算法不存在的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-12 23:30:47 | 显示全部楼层
本帖最后由 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)
                                                                          (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))
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-16 02:37 , Processed in 0.059811 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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