一维下料

aimisiyou

又发现几条排位规则：
1、当余料相同且项内最小毛坯相同时，按各项内最大毛坯长度由大到小排列；
2、当余料相同且项内最大、最小毛坯长度相同时，按最小毛坯个数由少到多排列。
故( ((0.45 0.45 0.45 0.45 0.2) 1 0) ((0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2) 1 0) ((0.8 0.8 0.2 0.2)1 0)((0.6 0.6 0.6 0.2)1 0)((0.8 0.7 0.45) 2 0.05)……）正确的排位为( ((0.8 0.8 0.2 0.2)1 0)((0.6 0.6 0.6 0.2)1 0)((0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2) 1 0) ((0.45 0.45 0.45 0.45 0.2) 1 0) ((0.8 0.7 0.45) 2 0.05)……）

aimisiyou

先定它一个小目标，解决形如((q1,q2,q3,……，qn) nk  d)迁移整合紧凑问题。其中q1>=q2>=q3>=……>=qn>0,d=（L-q1-q2-……qn）>=0。
显然：1、当d=0时，结果不变。
   2、当qn>d>0时且nk=1时，结果不变。   3、当nk=1时，结果不变。
   4、当qn>d>0时且nk>1时
       先判断（q1,q2,q3,……，qn，q1,q2,q3,……，qn）是否有连续几项和值与L的差值小于d,
       4.1若不存在，结果不变。
       4.2若存在，如L>=qi+q(i+1)+……qn+q1+q2+……qj=l1>L-d,  i>=2,j<n
              则((q1,q2,q3,……，qn) nk  d)
           =((q1,q2,q3,……，qn) (nk-2)  d)(q1,q2,q3,……，qn) 1  d)(q1,q2,q3,……，qn) 1  d)
          =((q1,q2,q3,……，qn) (nk-2)  d)(qi,q(i+1),……，qn，q1,q2……qj) 1  (L-l1))(q1,q2,q3,……，q(i-1),q(j+1),……，qn) 1  (2d+l1-L))
         若nk=偶数，则=((qi,q(i+1),……，qn，q1,q2……qj) (nk/2)  (L-l1))(q1,q2,q3,……，q(i-1),q(j+1),……，qn) (nk/2)  (2d+l1-L))
         若nk=偶数，则=((qi,q(i+1),……，qn，q1,q2……qj) (nk/2)  (L-l1)) (q1,q2,q3,……，qn) 1  d) (q1,q2,q3,……，q(i-1),q(j+1),……，qn) (nk/2)  (2d+l1-L))
     5、对结果按余料从小到大排序，结果形如（(（p1,p2,……pm1）nm1 dm1）(（p1,p2,……pm2）nm2 dm2）……(（p1,p2,……pm1）nmj  dmj））
     6、转至1。
     7、……（不知逻辑运算怎么下去了）

   举个例子，来找下思路。       （（1.1   0.4  0.3） 100   0.2）  当2*q1>L且d<qn时，感觉结果不变。
= （（1.1   0.4  0.3） 98  0.2）（1.1   0.4  0.3） 1  0.2）（1.1   0.4  0.3） 1  0.2））
=（（1.1   0.4  0.3） 98  0.2）（1.1  0.4  0.4）1   0.1）（1.1   0.3  0.3） 1   0.3）


      （（0.8   0.7   0.3） 100   0.2）=（（0.8  0.8   0.3）50  0.1）（0.7 0.7  0.3  0.3）25 0）（（0.7  0.7）25   0.6）  这种情形似乎也不变。判断理由？

     （（0.8   0.4  0.3   0.3） 100   0.2）      ；；；判断条件存在错误，即“每项差值均小于最小毛坯长度，故程序结束”不正确。
= （（0.8   0.4  0.3   0.3） 100   0.2）
=（（0.8  0.3  0.3  0.3  0.3）25   0）（0.8  0.8  0.4）37   0）（0.8  0.4  0.4  0.4）1  0）（（0.4   0.4   0.4   0.4  0.4） 12   0）

    （（0.5   0.4  0.3   0.3  0.3） 100   0.2）    ；；；判断条件存在错误，即“每项差值均小于最小毛坯长度，故程序结束”不正确。
=（（0.5  0.5  0.5  0.5）25  0）（（0.4  0.4  0.4  0.4  0.4） 20  0）（（0.3  0.3  0.3  0.3  0.3  0.3）50   0.2））

aimisiyou

通过验算，发现当毛坯规格为3个时，
（（q1,q2,q3）nk  d）  （其中q1>=q2>=q3,d<q3）时 可以通过迁移整体变得紧凑的必要条件是L-d<2*q1+q2<=L，否则不变（即nk是最少根数）。如（（1.1   0.4  0.3） 100   0.2）、 （（0.8   0.7   0.3） 100   0.2）均不能通过迁移而使得总根数变少,即此时nk为最少根数。

aimisiyou

_$ ;;;仅对规格种类为3，且余料小于等于最小毛坯长的情况
;;;形如((q1 q2 q3) n d),q1>=q2>=q3>=d
(defun f(lst)
   (setq q1 (car (car lst)))
   (setq q2 (cadr (car lst)))
   (setq q3 (caddr (car lst)))
   (setq n (cadr lst))
   (setq d (caddr lst))
   (setq L (+ q1 q2 q3 d))
   (if  (< n 6)
        (setq va lst)
                (if (= (rem n 6) 0)
                    (cond
                          ((and (<= (+ (* 2 q1) q2) L) (<= (+ (* 3 q2) q3) L) (<= (* 5 q3) L) )  
                             (setq va (vl-sort (list (list (list q1 q1 q2) (/ n 2) (- L q1 q1 q2 ))
                                         (list (list q2 q2 q2 q3) (/ n 6) (- L q2 q2 q2 q3))
                                         (list (list q3 q3 q3 q3 q3) (/ n 6) (- L q3 q3 q3 q3 q3))
                                                )
                                   '(lambda (e1 e2)
                                             (< (last e1) (last e2))
                                                                         )
                                                        )
                              )
                           )
                          ((and (<= (+ (* 3 q3) q1) L) (<= (+ (* 2 q1) q2) L) (<= (* 4 q2) L))  
                             (setq va (vl-sort (list (list (list q1 q1 q2) (/ n 3) (- L q1 q1 q2 ))
                                         (list (list q1 q3 q3 q3) (/ n 3) (- L q1 q3 q3 q3))
                                         (list (list q2 q2 q2 q2) (/ n 6) (- L q2 q2 q2 q2))
                                                )
                                   '(lambda (e1 e2)
                                             (< (last e1) (last e2))
                                                                         )
                                                        )
                              )
                           )
                          (t (setq va lst))
                         )
                    (cond
                          ((and (<= (+ (* 2 q1) q2) L) (<= (+ (* 3 q2) q3) L) (<= (* 5 q3) L))  
                             (setq va (vl-sort (list (list (list q1 q1 q2) (/ (- n (rem n 6)) 2) (- L q1 q1 q2 ))
                                         (list (list q2 q2 q2 q3) (/ (- n (rem n 6)) 6) (- L q2 q2 q2 q3))
                                         (list (list q3 q3 q3 q3 q3) (/ (- n (rem n 6)) 6) (- L q3 q3 q3 q3 q3))
                                                                     (list (list q1 q2 q3) (rem n 6) (- L q1 q2 q3 ))
                                                )
                                   '(lambda (e1 e2)
                                             (< (last e1) (last e2))
                                                                         )
                                                        )
                              )
                           )
                          ((and (<= (+ (* 3 q3) q1) L) (<= (+ (* 2 q1) q2) L) (<= (* 4 q2) L))  
                             (setq va (vl-sort (list (list (list q1 q1 q2) (/ (- n (rem n 6)) 3) (- L q1 q1 q2 ))
                                         (list (list q1 q3 q3 q3) (/ (- n (rem n 6)) 3) (- L q1 q3 q3 q3))
                                         (list (list q2 q2 q2 q2) (/ (- n (rem n 6)) 6) (- L q2 q2 q2 q2))
                                                                     (list (list q1 q2 q3) (rem n 6) (- L q1 q2 q3 ))
                                                 )
                                   '(lambda (e1 e2)
                                             (< (last e1) (last e2))
                                                                         )
                                                        )
                              )
                           )
                          (t (setq va lst))
                         )        
           )
  )
)
F
_$ (f '((1.1 0.4 0.3) 100 0.2))
((1.1 0.4 0.3) 100 0.2)
_$ (f '((0.8 0.4 0.3) 100 0.2))
((0.8 0.4 0.3) 100 0.2)
_$ (f '((0.6 0.4 0.3) 100 0.2))
((0.6 0.4 0.3) 100 0.2)
_$ (f '((45 29 23) 100 22))
(((45 45 29) 48 0) ((23 23 23 23 23) 16 4) ((29 29 29 23) 16 9) ((45 29 23) 4 22))
_$ (f '((40 20 20) 12 20))
(((40 40 20) 6 0) ((20 20 20 20 20) 2 0) ((20 20 20 20) 2 20))
_$ (f '((40 30 20) 12 20))
(((40 40 30) 6 0) ((30 30 30 20) 2 0) ((20 20 20 20 20) 2 10))
_$

aimisiyou

;;;形如((q1) n d)
(defun f1(lst)
   (setq q1 (car (car lst)))
   (setq n (cadr lst))
   (setq d (caddr lst))
   (setq L (+ q1 d))
   (if (= n 1)
       (setq va lst)
       (if (> (* 2 q1) L)
           (setq va lst)
                   (if (< (* q1 n) d)
                   (progn
                     (setq lst1 nil )
                         (repeat n (setq lst1 (cons q1 lst1)))
                     (setq va (list lst1 1 (- L (* q1 n))))
                        )
                   (progn
                    (setq i (fix (/ L q1)) j (rem n i) lst1 nil lst2 nil)
                        (repeat i (setq lst1 (cons q1 lst1)))
                (repeat j (setq lst2 (cons q1 lst2)))
                    (setq va (cons (list lst1 (/ n i) (- L (* q1 i))) (list (list lst2 1 (- L (* q1 j))))))
                       )
            )
         )
     )
)
F1
_$ (f1 '((7) 7 26))
(((7 7 7 7) 1 5) ((7 7 7) 1 12))
_$ (f1 '((7) 17 26))
(((7 7 7 7) 4 5) ((7) 1 26))
_$ (f1 '((7) 3 2))
((7) 3 2)
_$ (f1 '((7) 3 12))
(((7 7) 1 5) ((7) 1 12))
_$ (f1 '((7) 13 52))
(((7 7 7 7 7 7 7 7) 1 3) ((7 7 7 7 7) 1 24))
_$

aimisiyou

;;;形如((q1 q2) n d),q1>=q2
(defun f2(lst)
   (setq q1 (car (car lst)))
   (setq q2 (cadr (car lst)))
   (setq n (cadr lst))
   (setq d (caddr lst))
   (setq L (+ q1 q2 d))
   (if (< d q2)
       (setq va lst)
       (if  (< n 3)
            (setq va lst)
                      (if (= (rem n 3) 0)
                          (cond
                                ((and (<= (+ (* 2 q1) q2) L))  
                                  (setq va (vl-sort (list (list (list q1 q1 q2) (/ n 3) (- L q1 q1 q2))
                                              (list (list q1 q2 q2) (/ n 3) (- L q1 q2 q2))
                                                )
                                   '(lambda (e1 e2)
                                             (< (last e1) (last e2))
                                                                         )
                                                        )
                                     )
                                 )
                                         (t (setq va lst))
                                   )
                          (cond
                                 ((and (<= (+ (* 2 q1) q2) L))  
                                   (setq va (vl-sort (list (list (list q1 q1 q2) (/ (- n (rem n 3)) 3) (- L q1 q1 q2))
                                              (list (list q1 q2 q2) (/ (- n (rem n 3)) 3) (- L q1 q2 q2))
                                                                          (list (list q1 q2) (rem n 3) (- L q1 q2))
                                                     )
                                       '(lambda (e1 e2)
                                             (< (last e1) (last e2))
                                                                             )
                                                               )
                                    )
                                         )
                                         (t (setq va lst))
                               )
                                 )
                         )        
           )
)
_$  (f2 '((7 5) 14 7))
(((7 7 5) 4 0) ((7 5 5) 4 2) ((7 5) 2 7))
_$ (f2 '((7 5) 2 7))
((7 5) 2 7)
_$ (f2 '((7 5) 14 9))
(((7 7 5) 4 2) ((7 5 5) 4 4) ((7 5) 2 9))
_$ (f2 '((7 5) 14 13))
(((7 7 5) 4 6) ((7 5 5) 4 8) ((7 5) 2 13))

aimisiyou

_$  (defun fun(lst L)
(setq lst (vl-sort (vl-remove nil (mapcar '(lambda (x) (if (= (last x) 0) nil x)) lst)) '(lambda (a b) (if (= (last a) (last b)) (> (car a) (car b)) (> (last a) (last b))))))
(if (< (length lst) 2)
    (if (= (length lst) 1)
            (setq va (list (list (list (car (car lst))) (cadr (car lst))  (- L (car (car lst))))))
                (setq va nil)
        )
  (progn  
   (setq i 0 sum 0 vlst nil vvlst nil)
   (while (and (> L (setq sum (+ sum (if lst (car (nth i lst)) 0)))) (> (length lst) 0))
          (setq vlst (cons (car (nth i lst)) vlst))
                  (setq vvlst (cons (nth i lst) vvlst))
          (setq lst (cdr lst))
   )
   (setq nmin (apply 'min  (mapcar 'last vvlst)))
   (setq valst (reverse (cons (- L (apply '+ vlst))(cons nmin (list (vl-sort vlst '>))))))
   (setq vvlst (mapcar 'list (mapcar 'car vvlst)  (mapcar '(lambda (x) (- x nmin)) (mapcar 'last vvlst) )))
   (setq lst (append vvlst lst))
   (setq va (cons valst (fun lst L)))
  )
)
)
FUN
_$ (setq lst '((3 16)(10 11)(5 16)(9 12)(7 5) (8 10) (6 4)(11 4)) L 16)
16
_$ (fun lst L)
(((5 3) 16 8) ((9) 12 7) ((10) 11 6) ((8 7) 5 1) ((8) 5 8) ((11) 4 5) ((6) 4 10))
_$ (fun '((5.12 968) (4.73 88) (3.92 440) (3.62 880) (3.52 176) (3.32 528) (3.12  484)(3.02 770)(2.92 264) (2.64 44)(2.52 22) (2.38 88) (1.72 176) (1.585 88)) 12)
(((5.12 3.62 3.02) 770 0.24) ((3.92 3.32 3.12) 440 1.64) ((5.12 3.52 2.92) 176 0.44) ((4.73 3.62 1.72) 88 1.93) ((3.32 2.92 2.38 1.72 1.585) 88 0.075) ((5.12 3.12 2.64) 22 1.12) ((3.62 3.12 2.64 2.52) 22 0.1))
_$ (apply '+ (mapcar 'cadr (fun '((5.12 968) (4.73 88) (3.92 440) (3.62 880) (3.52 176) (3.32 528) (3.12  484)(3.02 770)(2.92 264) (2.64 44)(2.52 22) (2.38 88) (1.72 176) (1.585 88)) 12)))
1606

aimisiyou

_$ (defun fun1(lst L)
(setq lst (vl-sort (vl-remove nil (mapcar '(lambda (x) (if (= (last x) 0) nil x)) lst)) '(lambda (a b)  (> (* (car a) (cadr a)) (* (car b) (cadr b))))))
(if (< (length lst) 2)
    (if (= (length lst) 1)
            (setq va (list (list (list (car (car lst))) (cadr (car lst))  (- L (car (car lst))))))
                (setq va nil)
        )
  (progn  
   (setq i 0 sum 0 vlst nil vvlst nil)
   (while (and (> L (setq sum (+ sum (if lst (car (nth i lst)) 0)))) (> (length lst) 0))
          (setq vlst (cons (car (nth i lst)) vlst))
                  (setq vvlst (cons (nth i lst) vvlst))
          (setq lst (cdr lst))
   )
   (setq nmin (apply 'min  (mapcar 'last vvlst)))
   (setq valst (reverse (cons (- L (apply '+ vlst))(cons nmin (list (vl-sort vlst '>))))))
   (setq vvlst (mapcar 'list (mapcar 'car vvlst)  (mapcar '(lambda (x) (- x nmin)) (mapcar 'last vvlst) )))
   (setq lst (append vvlst lst))
   (setq va (cons valst (fun1 lst L)))
  )
)
)
FUN1
_$ (defun fun2(lst L)
(setq lst (vl-sort (vl-remove nil (mapcar '(lambda (x) (if (= (last x) 0) nil x)) lst)) '(lambda (a b) (if (= (last a) (last b)) (> (car a) (car b)) (> (last a) (last b))))))
(if (< (length lst) 2)
    (if (= (length lst) 1)
            (setq va (list (list (list (car (car lst))) (cadr (car lst))  (- L (car (car lst))))))
                (setq va nil)
        )
  (progn  
   (setq i 0 sum 0 vlst nil vvlst nil)
   (while (and (> L (setq sum (+ sum (if lst (car (nth i lst)) 0)))) (> (length lst) 0))
          (setq vlst (cons (car (nth i lst)) vlst))
                  (setq vvlst (cons (nth i lst) vvlst))
          (setq lst (cdr lst))
   )
   (setq nmin (apply 'min  (mapcar 'last vvlst)))
   (setq valst (reverse (cons (- L (apply '+ vlst))(cons nmin (list (vl-sort vlst '>))))))
   (setq vvlst (mapcar 'list (mapcar 'car vvlst)  (mapcar '(lambda (x) (- x nmin)) (mapcar 'last vvlst) )))
   (setq lst (append vvlst lst))
   (setq va (cons valst (fun2 lst L)))
  )
)
)
FUN2
_$ (fun1 '((11 4) (10 11) (9 12) (8 10) (7 5) (6 4) (5 16)(3 16)) 16)
(((10) 11 6) ((9) 12 7) ((8 5) 10 3) ((11 3) 4 2) ((7 5 3) 5 1) ((6 5 3) 1 2) ((6 3) 3 7) ((3) 3 13))
_$ (fun2 '((11 4) (10 11) (9 12) (8 10) (7 5) (6 4) (5 16)(3 16)) 16)
(((5 3) 16 8) ((10) 11 6) ((9) 12 7) ((8) 10 8) ((11) 4 5) ((7 6) 4 3) ((7) 1 9))
_$ (apply '+ (mapcar 'cadr (fun1 '((11 4) (10 11) (9 12) (8 10) (7 5) (6 4) (5 16)(3 16)) 16)))
49
_$ (apply '+ (mapcar 'cadr (fun2 '((11 4) (10 11) (9 12) (8 10) (7 5) (6 4) (5 16)(3 16)) 16)))
58
_$
_$ (vl-sort (fun1 '((5.12 968) (4.73 88) (3.92 440) (3.62 880) (3.52 176) (3.32 528) (3.12  484)(3.02 770)(2.92 264) (2.64 44)(2.52 22) (2.38 88) (1.72 176) (1.585 88)) 12) '(lambda (a b) (> (car (car a)) (car (car b)))))
(((5.12 3.62 3.02) 770 0.24) ((5.12 3.52 2.92) 176 0.44) ((5.12 3.12 2.64) 22 1.12) ((4.73 3.62 1.72) 88 1.93) ((3.92 3.32 3.12) 440 1.64) ((3.62 3.12 2.64 2.52) 22 0.1) ((3.32 2.92 2.38 1.72 1.585) 88 0.075))
_$

可见，按数量*长度排序比单独按数量排序的结果要优很多。

aimisiyou

初步想了个动态规划方程。
F（L，（l1,n1）,（l2,n2）,（l3,n3）……（lk,nk））=0,(if  0=l1*n1+l2*n2+……lk*nk)
F（L，（l1,n1）,（l2,n2）,（l3,n3）……（lk,nk））=1,(if  0<l1*n1+l2*n2+……lk*nk<=L)
F（L，（l1,n1）,（l2,n2）,（l3,n3）……（lk,nk））=1+min{F（L，（l1,n1-i1）,（l2,n2-i2）,（l3,n3-i3）……（lk,nk-ik））},( l1*i1+l2*i2+……lk*ik<=L)
i1、i2、i3、……ik>=0

aimisiyou

_$ (defun fun1(L lst)
   (if (= (length lst) 1)
       (if (< L (car lst))
               (setq va (list nil))
               (setq va (list (cons (car lst) (car (fun1 (- L (car lst)) lst)))))
            )
                (if (>= L (car lst))
            (setq va (append
                     (mapcar '(lambda (x) (cons (car lst) x)) (fun1 (- L (car lst)) lst))
                     (fun1 L (cdr lst))
                  )
             )
                         (setq va (fun1 L (cdr lst)))
                )
    )
)
FUN1
_$ (fun1 10 '(5.6 4.4))
((5.6 4.4) (4.4 4.4))
_$ (fun1 20 '(5.6 4.4))
((5.6 5.6 5.6) (5.6 5.6 4.4 4.4) (5.6 4.4 4.4 4.4) (4.4 4.4 4.4 4.4))
_$ (fun1 30 '(5.6 4.4))
((5.6 5.6 5.6 5.6 5.6) (5.6 5.6 5.6 5.6 4.4) (5.6 5.6 5.6 4.4 4.4) (5.6 5.6 4.4 4.4 4.4 4.4) (5.6 4.4 4.4 4.4 4.4 4.4) (4.4 4.4 4.4 4.4 4.4 4.4))
_$
奇怪？为什么30分解中，没有 (5.6 5.6 5.6 4.4 4.4 4.4)这一项？_$ (fun1 300 '(56 44))
((56 56 56 56 56) (56 56 56 56 44) (56 56 56 44 44 44) (56 56 44 44 44 44) (56 44 44 44 44 44) (44 44 44 44 44 44))
_$

aimisiyou

_$ (fun1 4.4 '(4.4))
((4.4))
_$ (fun1 8.8 '(4.4))
((4.4 4.4))
_$  (fun1 13.2 '(4.4))
((4.4 4.4))
_$  (fun1 17.6 '(4.4))
((4.4 4.4 4.4 4.4))
_$ (fun1 22 '(4.4))
((4.4 4.4 4.4 4.4 4.4))
_$ (fun1 26.4 '(4.4))
((4.4 4.4 4.4 4.4 4.4 4.4))
_$
这是什么原因？唯独3倍的情况出错。

aimisiyou

_$ (fun1 9.0 '(3.0))
((3.0 3.0 3.0))
_$ (fun1 9.3 '(3.1))
((3.1 3.1 3.1))
_$  (fun1 9.6 '(3.2))
((3.2 3.2))
_$
直接懵了
(setq i 0 n 500 nlst nil)
(while (< i n)
  (setq i (+ i 1))
  (if (= i (length (car (fun1 (* 3.3 i) '(3.3)))))
      (setq nlst (cons i nlst))
  )
)(reverse nlst)
nil
(500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 421 420 419 418 417 416 415 414 413 412 411 410 409 408 407 406 405 404 403 402 401 400 399 398 397 396 395 394 393 392 391 390 389 388 387 386 385 384 383 382 381 380 379 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 305 304 303 302 301 300 299 298 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 2 1)
(1 2 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500)
_$

aimisiyou

_$ (defun H_L (lst L)
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (> (+ x y) L) x (+ x y))
                                  y   
                                 (if  (> (+ x y) L)
                                                                          (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)) L)
                                                              (if (>= (car x)  (car y))
                                                                       (list
                                                                                (car x)
                                                                                (cadr y)
                                                                                (last 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)
                      )
            )
   )
  (cons (car (car lst1))(list (last (car lst1))))
)
H_L
_$
_$ (H_L '(5.12 4.73 3.92 3.62 3.52 3.32 3.12 2.92 2.64 2.54 2.38 1.75 1.585) 12)
(12.0 (2.64 2.92 3.32 3.12))
_$

aimisiyou

_$ (defun H_L (lst L)
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (> (+ x y) L) x (+ x y))
                                  y   
                                 (if  (> (+ x y) L)
                                                                          (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)) L)
                                                              (if (>= (car x)  (car y))
                                                                       (list
                                                                                (car x)
                                                                                (cadr y)
                                                                                (last 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)
                      )
            )
   )
  (cons (car (car lst1))(list (last (car lst1))))
)
H_L
_$
(H_L '(5.12 4.73 3.92 3.62 3.52 3.32 3.12 3.02 2.92 2.64 2.54 2.38 1.75 1.585) 12)
(11.7 (2.64 2.92 3.12 3.02))
_$随即调整lst（限定最大调整次数Nmax）,保留最优组合。_$ (H_L '(3.02 4.73 3.92 3.62 3.52 3.32 3.12  2.92 2.64 2.54 2.38 1.75 1.585 5.12) 12)
(12.0 (2.64 2.92 3.32 3.12))
_$
2,64个数最少为44个，则重复取44次此组合，得（44 （12 （2.64 2.92 3.32 3.12）），剩余(5.12/968 4.73/88 3.92/440  3.62/880  3.52 /176  3.32 /484  3.12/440  3.02/770  2.92/220  2.54/22   2.38/88 1.75/176 1.585/88)



_$ (H_L '(3.02 4.73 3.92 3.62 3.52 3.32 3.12  2.92 2.54 2.38 1.75 1.585 5.12) 12)
(11.9 (2.54 2.92 3.32 3.12))
_$ (H_L '(3.02 4.73  3.62 3.52 3.32 3.12  2.92 3.92 2.54 2.38 1.75 1.585 5.12) 12)
(11.87 (3.52 4.73 3.62))
_$ (H_L '(3.02 3.62 3.52 3.32 3.12  2.92 3.92 2.54 2.38 4.73 1.75 1.585 5.12) 12)
(11.76 (2.38 2.54 2.92 3.92))
_$ (H_L '(3.02 3.62 3.52 3.32 5.12 3.12  2.92 3.92 2.54 2.38 4.73 1.75 1.585 ) 12)
(11.96 (5.12 3.52 3.32))
_$

此时，3.52个数最少为176，故重复取176次（176 （11.96 （5.12 3.52 3.32）），剩余(5.12/792 4.73/88 3.92/440  3.62/880   3.32 /484  3.12/264 3.02/770  2.92/220  2.54/22   2.38/88 1.75/176 1.585/88)

_$ (H_L '(3.02 3.62 3.32 5.12 1.585 3.12  2.92 3.92 2.54  2.38 4.73 1.75  ) 12)
(11.76 (2.38 2.54 2.92 3.92))
_$ (H_L '( 3.62 3.32 5.12 1.585 3.12  2.92 3.92 2.54  2.38 4.73 3.02 1.75  ) 12)
(11.88 (1.75 3.02 2.38 4.73))
_$ (H_L '(5.12 1.585 3.12  2.92 3.92 2.54  2.38 4.73 3.02 3.32 3.62 1.75) 12)
(11.76 (2.38 2.54 2.92 3.92))
_$

最大值为11.88，此时2.54根数最少为22根，故重复选取22次，剩余(5.12/792  4.73/66 3.92/440  3.62/880   3.32 /462   3.12/264  3.02/748   2.92/220    2.38/66   1.75/154   1.585/88)

_$ (H_L '( 3.62 3.32 5.12 1.585 3.12  2.92 3.92  2.38 4.73 3.02 1.75  ) 12)
(11.88 (1.75 3.02 2.38 4.73))
_$  (H_L '( 3.62 3.32  1.585 3.12  2.92 3.92 5.12 2.38 4.73 3.02 1.75  ) 12)
(11.96 (5.12 2.92 3.92))
_$  (H_L '( 3.62 3.32  1.585 3.12  2.92 3.92 5.12  4.73 3.02 1.75 2.38 ) 12)
(11.96 (5.12 2.92 3.92))
_$ 最大值为11.96，此时2.92根数最少为220根，重复取220次，剩余(5.12/572 4.73/66 3.92/220  3.62/880   3.32 /462 3.12/264  3.02/748  2.54/22   2.38/66   1.75/154   1.585/88)


_$ (H_L '( 3.62 3.32  1.585 3.12  3.92 5.12  4.73 3.02 1.75 2.38 ) 12)
(11.945 (3.92 3.12 3.32 1.585))
_$  (H_L '( 3.62 3.32  1.585 3.12  3.92   4.73 3.02 5.12 1.75 2.38 ) 12)
(11.945 (3.92 3.12 3.32 1.585))
_$ (H_L '(  3.32  1.585 3.12  3.92 3.62  4.73 3.02 5.12 1.75 2.38 ) 12)
(11.945 (3.92 3.12 3.32 1.585))
_$ 最大值为11.945，此时1.585根数最少为88，重复取88次，剩余(5.12/572 4.73/66 3.92/132  3.62/880   3.32 /374    3.12/180  3.02/748  2.54/22   2.38/66   1.75/154 )


_$ (H_L '( 5.12  3.32  3.12  3.02 1.75 3.62  4.73 3.92   2.38 ) 12)
(11.56 (3.12 5.12 3.32))
_$ (H_L '( 5.12 4.73 3.32  3.12  3.02 1.75 3.62   3.92   2.38 ) 12)
(11.67 (2.38 3.92 1.75 3.62))
_$ (H_L '( 5.12 4.73 3.62 3.32  3.12  3.02 1.75    3.92   2.38 ) 12)
(11.81 (3.92 1.75 3.12 3.02))
_$ (H_L '( 5.12 4.73 3.92 3.62 3.32  3.12  3.02 1.75      2.38 ) 12)
(11.97 (3.32 4.73 3.92))
_$ (H_L '( 5.12 4.73 3.92 3.62 3.32  3.12  3.02  2.38 1.75      ) 12)
(11.97 (3.32 4.73 3.92))
_$

最大值为11.97，此时4.73根数最少为66根，剩余(5.12/572  3.92/66 3.62/880   3.32 /308    3.12/180  3.02/748    2.38/66   1.75/154 )

_$  (H_L '( 5.12 3.92 3.62 3.32  3.12  3.02  2.38 1.75      ) 12)
(11.84 (2.38 3.02 3.32 3.12))
_$  (H_L '(  3.92 3.62 3.32  3.12 5.12 3.02  2.38 1.75      ) 12)
(11.56 (5.12 3.32 3.12))
_$ (H_L '(  3.92  3.32 2.38 3.12 5.12 3.02 3.62  1.75      ) 12)
(11.76 (3.62 5.12 3.02))
_$ (H_L '(  3.92 1.75  3.32 2.38 3.12 5.12 3.02 3.62      ) 12)
(11.76 (3.62 5.12 3.02))
_$ (H_L '(  3.92 1.75  3.32 5.12 2.38 3.12  3.02 3.62      ) 12)

最大值为11.84，此时2.38根数最少为66根，剩余(5.12/572  3.92/66  3.62/880   3.32 /242   3.12/114  3.02/ 616   1.75/154 )

_$ (H_L '(  3.92 3.62  3.32 5.12 3.12 1.75 ) 12)
(11.56 (3.12 3.32 5.12))
_$ (H_L '(  3.92 3.12 3.62  3.32 5.12  1.75 ) 12)
(11.81 (1.75 3.32 3.12 3.62))
_$ (H_L '(  3.92  3.62 3.12 3.32 5.12  1.75 ) 12)
(11.56 (5.12 3.12 3.32))
_$ (H_L '(  3.92 1.75 3.62 3.12 3.32 5.12   ) 12)
(11.81 (3.32 3.12 1.75 3.62))
_$
最大值11.81，此时,3.12根数最少为114根，剩余(5.12/572  3.92/66  3.62/766  3.32 /128    3.02/ 616   1.75/40)

_$ (H_L '( 5.12 3.92 3.62  3.32 3.02 1.75 ) 12)
(11.71 (1.75 3.02 3.62 3.32))
_$  (H_L '( 3.92 3.62  3.32 5.12 3.02 1.75 ) 12)
(11.46 (3.02 3.32 5.12))
_$ (H_L '( 3.92   3.32 5.12 3.02 3.62 1.75 ) 12)
(11.76 (3.62 5.12 3.02))
_$

最大值为11.76，此时,5.12根数最少为572根，剩余(3.92/66  3.62/194  3.32 /128    3.02/ 44   1.75/40)


_$ (H_L '(    3.32 3.62 3.02 3.92 1.75 ) 12)
(10.56 (3.92 3.62 3.02))
_$ (H_L '( 1.75   3.32 3.62 3.02 3.92  ) 12)
(11.71 (3.02 3.62 1.75 3.32))
_$ (H_L '( 1.75  3.62  3.32 3.02 3.92  ) 12)
(11.71 (3.02 3.32 1.75 3.62))
_$
最大值为11.71，此时,1.75根数最少为40根，剩余(3.92/66  3.62/154  3.32 /88    3.02/ 4)

_$ (H_L '( 3.62 3.92 3.32 3.02   ) 12)
(10.86 (3.32 3.62 3.92))
_$  (H_L '( 3.32 3.62 3.92 3.02   ) 12)
(10.86 (3.92 3.32 3.62))
_$ 最大值为10.86，此时,3.92根数最少为66根，剩余( 3.62/88 3.32 /22  3.02/ 4)


_$  (H_L '( 3.02 3.62  3.32 ) 12)
(9.96 (3.32 3.02 3.62))
_$ 最大值为9.96，此时,3.02根数最少为4根，剩余( 3.62/84 3.32 /18 )



_$  (H_L '( 3.62  3.32 ) 12)
(6.94 (3.62 3.32))
_$ 最大值为6.94，此时,3.32根数最少为18根，剩余( 3.62/66)



3.62+3.62+3.62=10.86
66/3=22次

总根数为44+176+22+220+88+66+66+114+572+40+66+4+18+22=1518根。

aimisiyou

整个程序笔算走一遍，就会发现很多问题：
1、当(H_L lst L)离L较远，但和值再加上一个数值（如lst中最小值）却离L很近时，也要保留这种情况，即组合中加上该数值；如_$ _$ (H_L '(5.12 3.32 3.92 1.75 3.62) 12)
(10.19 (1.75 5.12 3.32)) 加上1.75=11.94<12,故组合为（1.75 1.75 5.12 3.32）
2、贪心算法前面组合很紧凑，但后面就不好凑合了，结果情况有时很差；
3、如果(H_L lst L)和(H_L lst’ L)和值相等，取其中最大值较大的那组，原因先消耗掉长度长的零件；
4、对于那些（n+1）li稍大于L,n*Li离L又较远的数值li，（比较密集的如3.32,3.12,3.02）应分开到不同的组合中（和值接近L）消耗掉，尽量别最后集中在一起.
5、若随机次数达到，但最大和值组合结果仍不理想（比如组合利用率不到90%），随机选择一个数值（大数的数概率大，小数的概率小）添加到lst中，进行组合。
6、对于那些（n+1）li稍大于L,n*Li离L又较远的数值li，（比较密集的如3.32,3.12,3.02），分开搜寻组合；即（H_L  ’（……3.32……）12）  （H_L  ’（……3.12……）12）（H_L  ’（……3.02……）12）.或者即（H_L  ’（……3.32  3.12……）12）、即（H_L  ’（……3.32  3.02……）12）  即（H_L  ’（……3.12 3.02……）12）