和值固定的不同组合

aimisiyou

有一列数n1,n2,n3,n4……nk（按递减排列），如何从中选取一些数组成一组，使其和值为L？不同的组可以有哪些？

aimisiyou

先构造从1到2^K的所有二进制数，然后分别与（a1,a2……ak）点乘，再看其中是否有等于L的情况。

aimisiyou

如果要找出所有组合，运算量太大了，效率太低了。但若是找出其中一种组合即可，还是很快的，复杂度O（n^2）.

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))
                                                                       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)
                      )
            )
   )
  (last (car lst1))
)
H_L
_$ (H_L '(1 2 3 4 5 6 7 8)  25)
(7 6 5 3 4)
_$

aimisiyou

有时我们希望运行的结果能满足有一些限定条件，比如该组中必含某个数值。很简单。还是举例比如我们想从‘（1 2 3 4 5 6 7 8 9）选出一些数值，使其和值等于25，但该组中必须含数值9。也就是要从（1 2 3 4 5 6 7 8 ）中选出一些数组成和值为16.注意一点，（1 2 3 4 5 6 7 8 ）必须安降序排列，
即求（H_L '（8,7 6 5 4 3 2 1） 16）。

_$ (H_L '(8 7 6 5 4 3 2 1)  16)
(1 4 6 5)
_$

而_$ (H_L '(1 2 3 4 5 6 7 8)  16)
(5 4 3 1 2)  是不对的。
所以必须按降序排列。

tzfcn

算法是关键，有了优秀的算法，就可以事半功倍。

aimisiyou

怎么出现错误，先标记下。
_$ (H_L '(103 65 41 39 35 27 21 17 3 97 89) 179)
(3 3 27 39 65 41)
_$

aimisiyou

_$ (setq lst '(4 5 7 6 1 2 3 8) L 20)
20
_$  (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)
               )
   )
-1
((9 5 (4 5)) (12 7 (5 7)) (13 6 (7 6)) (7 1 (6 1)) (3 2 (1 2)) (5 3 (2 3)) (11 8 (3 8)))
_$        (setq lst1 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) L)
                                                              (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)
                      )
            )
((16 7 (7 4 5)) (18 6 (6 5 7)) (14 1 (1 7 6)) (9 2 (2 6 1)) (6 3 (3 1 2)) (13 8 (8 2 3)))
_$        (setq lst1 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) L)
                                                              (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)
                      )
            )
((18 6 (6 5 7)) (19 1 (1 6 5 7)) (16 2 (2 1 7 6)) (12 3 (3 2 6 1)) (14 8 (8 3 1 2)))
_$        (setq lst1 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) L)
                                                              (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)
                      )
            )
((19 1 (1 6 5 7)) (19 1 (1 6 5 7)) (19 3 (3 2 1 7 6)) (20 8 (8 3 2 6 1)))
_$        (setq lst1 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) L)
                                                              (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)
                      )
            )
((20 1 (1 1 6 5 7)) (19 1 (1 6 5 7)) (20 8 (8 3 2 6 1)))
_$

找到了出错的原因了。

ynhh

加油

yzj63298368

感谢分享！！！！！！！！！！！！

cable2004

感谢分享！！！！！！！！！！！！

aimisiyou

aimisiyou 发表于 2019-11-8 22:27
_$ (setq lst '(4 5 7 6 1 2 3 8) L 20)
20
_$  (setq i -1)

_$ (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 '(103 65 41 39 35 27 21 17 3 97 89) 179)
(175 (3 27 39 65 41))
_$ (H_L '(4 5 7 6 1 2 3 8) 20)
(20 (8 3 2 6 1))
_$

aimisiyou

对于单一原材料L。裁成l1/n1根，l2/n2根……li/ni根,需要多少根原材料、如何下料问题。可以先按降序排列零件长度lst,按 (H_L lst  L)求出一组解，若解得总和等于L，则重复此组，直到零件长度lst减少一种零件；若解的总和小于L，只取一组，根数列表nlst相应减少，然后将最大零件长度移至中间位 ,再 (H_L lst’  L)，看是否有更好的组合。如果组合和值没变化，就将长度列表lst第一位移至最大零件长度的后后一位（间隔一位），再 (H_L lst’  L)，看是否有更好的组合……直到分解完。
最终汇总得到的下料方式是近似较好解。

aimisiyou

aimisiyou 发表于 2019-11-11 07:59
对于单一原材料L。裁成l1/n1根，l2/n2根……li/ni根,需要多少根原材料、如何下料问题。可以先按降序排列零 ...

思路不对，应该将所有的零件都排列进去，而不是仅仅是不同型号的零件，如l1要3个，l2要2个，l3要1个，则lst=(l1,l1,l1,l2,l2,l3),再按(H_L lst  L)来计算。不过为了加快运算，当所有型号的长度之和远大于L时，可以搜索下（l1,l2,l3……）是否有组合等于L，若果有，重复选取此组，直至零件种类少一种，然后快速减少nlst；如果（l1,l2,l3……）没有有组合等于L，则列出所有零件，如lst=(l1,l1,l1,l2,l2,l3)，按(H_L lst  L)搜索，若2*l1+l2=L,则nlst中，l1和l2按比例减少，直到又减少一种型号零件；……，最后nlst=nil分解完。属于贪心算法。

aimisiyou

aimisiyou 发表于 2019-11-11 07:59
对于单一原材料L。裁成l1/n1根，l2/n2根……li/ni根,需要多少根原材料、如何下料问题。可以先按降序排列零 ...

思路不对，应该将所有的零件都排列进去，而不是仅仅是不同型号的零件，如l1要3个，l2要2个，l3要1个，则lst=(l1,l1,l1,l2,l2,l3),再按(H_L lst  L)来计算。不过为了加快运算，当所有型号的长度之和远大于L时，可以搜索下（l1,l2,l3……）是否有组合等于L，若果有，重复选取此组，直至零件种类少一种，然后快速减少nlst；如果（l1,l2,l3……）没有有组合等于L，则列出所有零件，如lst=(l1,l1,l1,l2,l2,l3)，按(H_L lst  L)搜索，若2*l1+l2=L,则nlst中，l1和l2按比例减少，直到又减少一种型号零件；若(H_L lst  L)不等于L，则只取一组，nlst相应减少，剩余的lst随机排列成lst'，再(H_L lst’  L)搜索……，最后nlst=nil分解完。属于贪心算法。