设为首页收藏本站

晓东CAD家园-论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 55|回复: 14

和值固定的不同组合

[复制链接]

已领礼包: 1517个

财富等级: 堆金积玉

发表于 2019-11-8 17:31:31 | 显示全部楼层 |阅读模式

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

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

x
有一列数n1,n2,n3,n4……nk(按递减排列),如何从中选取一些数组成一组,使其和值为L?不同的组可以有哪些?
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 17:49:19 | 显示全部楼层
先构造从1到2^K的所有二进制数,然后分别与(a1,a2……ak)点乘,再看其中是否有等于L的情况。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 18:37:25 | 显示全部楼层
如果要找出所有组合,运算量太大了,效率太低了。但若是找出其中一种组合即可,还是很快的,复杂度O(n^2).
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 18:53:18 | 显示全部楼层
_$ (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)
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 19:17:02 | 显示全部楼层
有时我们希望运行的结果能满足有一些限定条件,比如该组中必含某个数值。很简单。还是举例比如我们想从‘(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)  是不对的。
所以必须按降序排列。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 3774个

财富等级: 富可敌国

发表于 2019-11-8 19:29:54 | 显示全部楼层
算法是关键,有了优秀的算法,就可以事半功倍。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 19:56:31 | 显示全部楼层
怎么出现错误,先标记下。
_$ (H_L '(103 65 41 39 35 27 21 17 3 97 89) 179)
(3 3 27 39 65 41)
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 2019-11-8 22:27:45 | 显示全部楼层
_$ (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)))
_$

找到了出错的原因了。

点评

_$ (defun H_L (lst L) (setq i -1) (setq lst1 (mapcar '(lambda (x y) (progn (setq i (+ i 1)) (list (if (>  详情 回复 发表于 7 天前
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

点击这里给我发消息

已领礼包: 5295个

财富等级: 富甲天下

发表于 2019-11-9 11:00:13 | 显示全部楼层
加油
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

已领礼包: 51个

财富等级: 招财进宝

发表于 2019-11-9 14:05:06 | 显示全部楼层
感谢分享!!!!!!!!!!!!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

已领礼包: 2225个

财富等级: 金玉满堂

发表于 7 天前 | 显示全部楼层

感谢分享!!!!!!!!!!!!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 7 天前 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-11 08:23 编辑
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))
_$


论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 7 天前 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-11 08:32 编辑

对于单一原材料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),看是否有更好的组合……直到分解完。
最终汇总得到的下料方式是近似较好解。

点评

思路不对,应该将所有的零件都排列进去,而不是仅仅是不同型号的零件,如l1要3个,l2要2个,l3要1个,则lst=(l1,l1,l1,l2,l2,l3),再按(H_L lst L)来计算。  详情 回复 发表于 7 天前
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 7 天前 | 显示全部楼层
本帖最后由 aimisiyou 于 2019-11-11 09:50 编辑
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分解完。属于贪心算法。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1517个

财富等级: 堆金积玉

 楼主| 发表于 7 天前 | 显示全部楼层
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分解完。属于贪心算法。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|小黑屋|手机版|Archiver|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )  

GMT+8, 2019-11-18 22:26 , Processed in 0.177319 second(s), 58 queries , Gzip On, WinCache On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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