采用动态规划求解0-1背包问题最优解

aimisiyou · 发表于 2019-12-18 01:36:06

本帖最后由 aimisiyou 于 2019-12-18 01:37 编辑

对于特殊值，突发想到另一种算法，就是先不考虑y值，将X数值分成两组，每组有N个单元，每单元中可以自由组合，两组单元一一对应，且满足单元组合数多的x的和值不小于另一组的和值。对于3,3,3,4,13,15,16，即可分为（（(3,3,3,4)(13)）((15)(16))）,然后按对应的Y值分成第一组大，第二组小，即
第一组：（（3,15）（3,11）（3，9）（4,12）），（15,90）
第二组：（13,26），（16,26）
对于某些特殊值X，可以很快求出最优解，如此就可以简化很多运算。基本上是尽量先取完第一组再取第二组。例如：
f(25)=f(15)+f(10)=90+15+11+12=128
f(29)=f(15)+f(13)=90+15+11+9+12=137f(41)=f(15)+f(13)+f(13)=90+15+11+9+12+26=153

aimisiyou · 发表于 2019-12-18 13:48:22

现在只考虑两个方框不相交的情况（若相交，减去其中的共同点wi,ci，问题转换为w_tol-wi）,若黄色方框内Y值大于蓝色方框内Y值之和，就减少黄色框内的一些点，替换成蓝色框中的一些点；,若黄色方框内Y值小于蓝色方框内Y值之和（很少见），就减少蓝色框内的一些点，替换成黄色框中的一些点。

aimisiyou · 发表于 2019-12-18 13:49:29

若是从黄框内减少点替换成蓝色框内的点，则将蓝色框内点按点到右直线（45度角）的距离降序排列，优先替换前面的（不一定是Y值最高点）；若是从蓝框内减少点替换成黄色框内的点，则将黄色框内点按点到左直线（45度角）的距离升序排列，优先替换前面的（不一定是Y值最高点）。若不存在替换的情况，那就是最优的结果。

aimisiyou · 发表于 2019-12-18 14:02:46

本帖最后由 aimisiyou 于 2019-12-18 14:04 编辑

为确保万无一失，减少黄色框内点替换成蓝色框内点时，还要加上中间小区域（三个并排点区域），即还可能替换成此区域内的点。

aimisiyou · 发表于 2019-12-21 17:47:13

根据贪心算法似乎找到了一个快速接近最优解的多项式算法。

aimisiyou · 发表于 2019-12-23 19:37:33

本帖最后由 aimisiyou 于 2019-12-23 19:51 编辑

(defun ff(nn ww_tol ppts_front pt)
  (setq k (- nn (length ppts_front)))
  (setq pt0 (last ppts_front))
  (setq ww_max (- (* (last pt)(- w_tol (apply '+ (mapcar 'car ppts_front)))) (* k (cadr pt))))
  (if (>= ww_max 0)
   (setq fva 0)
   (setq fva (/ (* (abs (/ ww_max (- ww_tol (apply '+ (mapcar 'car ppts_front)) (* k (car pt))))) (last pt))
               (last pt0)
   )
   )
  )
  fva
)
(setq  w_tol 550
   wlst '(24  14  45  35  19  33  50  58  80  27  72  25  66  62  83  42  55 71 59  45)
   clst '(70  38  93  70  36  56  80  90  120 38  99  30  89  77  94  43  49 62 48  29)
   n  (length wlst)
   flag t
   pts_lst nil
   pts_front nil
)
(setq rlst (mapcar '(lambda (wx wy) (/ wy 1.0 wx)) wlst clst))
(setq pts_front (vl-sort (mapcar '(lambda (x y z) (list x y z)) wlst clst rlst) '(lambda (ea eb) (> (caddr ea) (caddr eb)))))
(while flag
(setq  n1  (length pts_front))
(setq  n2 (/ n1 2))
(setq pts_lst (append (member (nth n2 pts_front) pts_front) pts_lst))
(setq pts_front (reverse (member (nth (- n2 1) pts_front) (reverse pts_front))))
(if (<= (apply '+ (mapcar 'car pts_front)) w_tol)
      (setq flag nil)
   )
)
(while (<= (apply '+ (mapcar 'car pts_front)) w_tol)
  (setq ptmax (cdr (car (vl-sort (mapcar '(lambda (ppt) (cons (ff n w_tol pts_front ppt) ppt)) pts_lst) '(lambda (ax bx) (> (car ax) (car bx)))))))
  (setq pts_front (reverse (cons ptmax (reverse pts_front))))
  (setq pts_lst (vl-remove ptmax pts_lst))
)
(list (apply '+ (mapcar 'car (reverse (cdr (reverse pts_front)))))
   (apply '+ (mapcar 'cadr (reverse (cdr (reverse pts_front)))))
   (reverse (cdr (reverse pts_front)))
)
FF
nil
(2.91667 2.71429 2.06667 2.0 1.89474 1.69697 1.6 1.55172 1.5 1.40741 1.375 1.2 1.34848 1.24194 1.13253 1.02381 0.890909 0.873239 0.813559 0.644444)
((24 70 2.91667) (14 38 2.71429) (45 93 2.06667) (35 70 2.0) (19 36 1.89474) (33 56 1.69697) (50 80 1.6) (58 90 1.55172) (80 120 1.5) (27 38 1.40741) (72 99 1.375) (66 89 1.34848) (62 77 1.24194) (25 30 1.2) (83 94 1.13253) (42 43 1.02381) (55 49 0.890909) (71 62 0.873239) (59 48 0.813559) (45 29 0.644444))
nil
((25 30 1.2) (83 94 1.13253) (42 43 1.02381) (55 49 0.890909) (71 62 0.873239) (59 48 0.813559) (45 29 0.644444))
(523 879 ((24 70 2.91667) (14 38 2.71429) (45 93 2.06667) (35 70 2.0) (19 36 1.89474) (33 56 1.69697) (50 80 1.6) (58 90 1.55172) (80 120 1.5) (27 38 1.40741) (72 99 1.375) (66 89 1.34848)))
_$

aimisiyou · 发表于 2019-12-23 20:03:32

(setq  w_tol 550
   wlst '(45  27 58 25 33 42 55 62 19 72 80 24 59 35 14 66 45 83 71 40)
   clst '(93 38 90 30 56 43 49 77 36 99 120 79 48 70 38 89 29 94 62 80)
   n  (length wlst)
   flag t
   pts_lst nil
)
_$
(513 888 ((24 79 3.29167) (14 38 2.71429) (45 93 2.06667) (35 70 2.0) (40 80 2.0) (19 36 1.89474) (33 56 1.69697) (58 90 1.55172) (80 120 1.5) (27 38 1.40741) (72 99 1.375) (66 89 1.34848)))

aimisiyou · 发表于 2019-12-23 20:07:58

(setq  w_tol 950
   wlst '(9 36 67 29 58 19 98 205 39 96 45 79 49 88 124 105 38 113 300 160)
   clst '(26 70 130 50 93 29 145 300 56 137 62 108 65 116 160 120 40 100 200)
   n  (length wlst)
   flag t
   pts_lst nil
)
_$
(917 1387 ((9 26 2.88889) (36 70 1.94444) (67 130 1.9403) (29 50 1.72414) (58 93 1.60345) (19 29 1.52632) (98 145 1.47959) (205 300 1.46341) (39 56 1.4359) (96 137 1.42708) (45 62 1.37778) (79 108 1.36709) (49 65 1.32653) (88 116 1.31818)))

aimisiyou · 发表于 2019-12-23 22:49:49

(defun ff(nn ww_tol ppts_front pt)
  (setq k (- nn (length ppts_front)))
  (setq pt0 (last ppts_front))
  (setq ww_max (- (* (last pt)(- w_tol (apply '+ (mapcar 'car ppts_front)))) (* k (cadr pt))))
  (if (>= ww_max 0)
   (setq fva 0)
   (setq fva (/ (* (abs (/ ww_max (- ww_tol (apply '+ (mapcar 'car ppts_front)) (* k (car pt))))) (last pt))
                     (last pt0)
                              )
         )
  )
  fva
)
(setq w_tol 1000
   wlst '(80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1)
         clst '(220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 58 56 50 30 20 15 10 8 5 3 1)
   n  (length wlst)
         flag t
   pts_lst nil
         pts_front nil
)
(setq rlst (mapcar '(lambda (wx wy) (/ wy 1.0 wx)) wlst clst))
(setq pts_front (vl-sort (mapcar '(lambda (x y z) (list x y z)) wlst clst rlst) '(lambda (ea eb) (> (caddr ea) (caddr eb)))))
(setq pts pts_front)
(while flag
      (setq  n1  (length pts_front))
(setq  n2 (/ n1 2))
(setq pts_lst (append (member (nth n2 pts_front) pts_front) pts_lst))
(setq pts_front (reverse (member (nth (- n2 1) pts_front) (reverse pts_front))))
(if (<= (apply '+ (mapcar 'car pts_front)) w_tol)
         (setq flag nil)
      )
)
(while (> (length pts_lst) 1)
(setq pts_lt  pts_lst nn (length pts_lst))
(setq pts_fro  pts_front )
(setq valst nil)
(repeat (- nn 1)
   (setq valst (cons (cons (ff n w_tol  pts_fro (car pts_lt)) (car pts_lt)) valst))
   (setq pts_fro (reverse (cons (car pts_lt) (reverse pts_front))))
   (setq pts_lt (cdr pts_lt))
)
(setq pt (cdr (car (vl-sort valst '(lambda (ax bx) (> (car ax) (car bx)))))))
(if (<= (+ (car pt)(apply '+ (mapcar 'car pts_front))) w_tol)
   (progn
      (setq pts_front (reverse (cons pt (reverse pts_front))))
      (setq pts_lst (vl-remove pt pts_lst))
   )
   (setq pts_lst nil)
   )
)
(list (apply '+ (mapcar 'car (reverse (cdr (reverse pts_front)))))
   (apply '+ (mapcar 'cadr (reverse (cdr (reverse pts_front)))))
   (reverse (cdr (reverse pts_front)))
)

aimisiyou · 发表于 2019-12-27 16:52:09

本帖最后由 aimisiyou 于 2019-12-27 16:59 编辑

问题可转化为已知点P0（x0,y0）和其他n个点p1（x1 ,y1）、p2(x2,y2)……pn(xn,yn)且yi均小于y0。要求从n个点中选出几个点，使得选中的点横坐标之和大于x0，纵坐标之和最小。

aimisiyou · 发表于 2020-1-3 15:19:40

_$ (defun ff(nn ww_tol ppts_front pt)
  (setq k (- nn (length ppts_front)))
  (setq pt0 (last ppts_front))
  (setq ww_max (- (* (last pt)(- w_tol (apply '+ (mapcar 'car ppts_front)))) (* k (cadr pt))))
  (if (>= ww_max 0)
   (setq fva 0)
   (setq fva (/ (* (abs (/ ww_max (- ww_tol (apply '+ (mapcar 'car ppts_front)) (* k (car pt))))) (last pt))
                     (last pt0)
                              )
         )
  )
  fva
)
(setq  w_tol 1000
   wlst '(80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1)
         clst '(220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 58 56 50 30 20 15 10 8 5 3 1)
   n  (length wlst)
         flag t
   pts_lst nil
)
(setq rlst (mapcar '(lambda (wx wy) (/ wy 1.0 wx)) wlst clst))
(setq pts_front (vl-sort (mapcar '(lambda (x y z) (list x y z)) wlst clst rlst) '(lambda (ea eb) (> (caddr ea) (caddr eb)))))
(while flag
      (setq  n1  (length pts_front))
(setq  n2 (/ n1 2))
(setq pts_lst (append (member (nth n2 pts_front) pts_front) pts_lst))
(setq pts_front (reverse (member (nth (- n2 1) pts_front) (reverse pts_front))))
(if (<= (apply '+ (mapcar 'car pts_front)) w_tol)
         (setq flag nil)
      )
)
(while (<= (apply '+ (mapcar 'car pts_front)) w_tol)
  (setq ptmax (cdr (car (vl-sort (mapcar '(lambda (ppt) (cons (ff n w_tol pts_front ppt) ppt)) pts_lst) '(lambda (ax bx) (> (car ax) (car bx)))))))
  (setq pts_front (reverse (cons ptmax (reverse pts_front))))
  (setq pts_lst (vl-remove ptmax pts_lst))
)
(list (apply '+ (mapcar 'car (reverse (cdr (reverse pts_front)))))
   (apply '+ (mapcar 'cadr (reverse (cdr (reverse pts_front)))))
   (reverse (cdr (reverse pts_front)))
)
FF
nil
(2.75 2.53659 2.32941 2.74286 2.5 2.57143 2.5 3.24 2.90909 6.32 3.1 2.36364 3.125 2.54167 2.4 3.6875 5.22727 1.83333 3.5 3.15625 2.5 2.63158 2.8 3.0 3.8 3.21429 2.93333 3.72727 1.6 2.56667 1.66667 2.43333 1.2 1.4 3.45 1.01538 3.25 2.52 1.93333 5.6 2.5 1.2 1.33333 1.5 1.0 0.8 1.25 0.75 0.5)
((25 158 6.32) (10 56 5.6) (22 115 5.22727) (25 95 3.8) (22 82 3.72727) (32 118 3.6875) (30 105 3.5) (20 69 3.45) (20 65 3.25) (50 162 3.24) (28 90 3.21429) (32 101 3.15625) (40 125 3.125) (50 155 3.1) (32 96 3.0) (30 88 2.93333) (55 160 2.90909) (35 98 2.8) (80 220 2.75) (70 192 2.74286) (38 100 2.63158) (70 180 2.57143) (30 77 2.56667) (48 122 2.54167) (82 208 2.53659) (25 63 2.52) (72 180 2.5) (66 165 2.5) (40 100 2.5) (20 50 2.5) (30 73 2.43333) (50 120 2.4) (55 130 2.36364) (85 198 2.32941) (30 58 1.93333) (60 110 1.83333) (45 75 1.66667) (50 80 1.6) (10 15 1.5) (50 70 1.4) (15 20 1.33333) (4 5 1.25) (60 72 1.2) (25 30 1.2) (65 66 1.01538) (10 10 1.0) (10 8 0.8) (4 3 0.75) (2 1 0.5))
nil
((72 180 2.5) (66 165 2.5) (40 100 2.5) (20 50 2.5) (30 73 2.43333) (50 120 2.4) (55 130 2.36364) (85 198 2.32941) (30 58 1.93333) (60 110 1.83333) (45 75 1.66667) (50 80 1.6) (10 15 1.5) (50 70 1.4) (15 20 1.33333) (4 5 1.25) (60 72 1.2) (25 30 1.2) (65 66 1.01538) (10 10 1.0) (10 8 0.8) (4 3 0.75) (2 1 0.5))
(976 3037 ((25 158 6.32) (10 56 5.6) (22 115 5.22727) (25 95 3.8) (22 82 3.72727) (32 118 3.6875) (30 105 3.5) (20 69 3.45) (20 65 3.25) (50 162 3.24) (28 90 3.21429) (32 101 3.15625) (40 125 3.125) (50 155 3.1) (32 96 3.0) (30 88 2.93333) (55 160 2.90909) (35 98 2.8) (80 220 2.75) (70 192 2.74286) (38 100 2.63158) (70 180 2.57143) (30 77 2.56667) (48 122 2.54167) (82 208 2.53659)))
_$

账号		自动登录	找回密码
密码			立即注册

[原创] 采用动态规划求解0-1背包问题最优解