二维下料

aimisiyou

;;;当DA DB均为a的倍数，且均不为b的倍数时，a>b
(defun f1(DA DB a b)
   (setq a1 (/ DA a) det (- a b))
   (setq top (rem DB b) at  (/ top det ) )
   (setq b1 (- (/ DB b) at))
   (if (or (< (* (- DA a)(- DB b)) 0)  (< (* (- DA b)(- DB a)) 0)  (< (* DA DB) (* a b)) (= b1 0)  )
       (setq va 0)
       (setq va (+ (* a1 b1) (f1 (* at a) DA a b)))
    )
  va
)
(f1 100  200 10 7) =284
(f1 200 100 10 7) =280

(f1 300 400 10 7)=1710
(f1 400 300 10 7)=1714

aimisiyou

;;;假设DA、DB均是b的倍数，且都不是a的倍数   a>b
(defun f2(DA DB a b)
   (setq a1 (/ DA b) det (- a b))
   (setq top (rem DB a) at  (/ (- b top) det ) )
   (setq b1 (- (/ DB a) at))
   (if (or (< (* (- DA a)(- DB b)) 0)  (< (* (- DA b)(- DB a)) 0)  (< (* DA DB) (* a b))  )
       (setq va 0)
       (if (= b1 0)  
           (setq va (* a1 (/ DB a)))
           (setq va (+ (* a1 b1) (f2 (* (+ 1 at) b) DA a b)))  
       )
    )
  va
)
(f2 200 100 11 10)=180
(f2 100 200 11 10)=181

(f2 2000 1000 60 50)=664
(f2 1000 2000 60 50)=666

aimisiyou

接下来考虑一种情况，DA、DB均为a,b的线性组合，令DA=k1*a+k2*b,DB=k3*a+k4*b,那么
能获得的总数为n=k1*k4+k2*k3+max{(f1 (k1*a) (k3*a) a b),(f1 (k3*a) (k1*a) a b)}+max{(f2 (k2*b) (k4*b) a b),(f2 (k4*b) (k2*b) a b)},对各种组合情况计算，取n的最大值

aimisiyou

当然n不一定是最优值（运气好的话可能碰上），但可作为实际操作中的下限值考虑。

aimisiyou

接着说，DA相对DB较大（暂不考虑线性分解），DB为a，b的线性组合，令DB=k3*a+k4*b,(注意此时k3取能取到的最大值，待会说明原因)，然后在DA上取长度k4*a+k3*b构成一个矩形，（此时在DA上的距离是最短的，解释前面k3取最大值原因，也是为了把机会多留给后面），此矩形由（k3+k4）^2个构件围成，中间有k3*k4个空隙，材料利用率高。如DB=3*a+2*b的情况。

aimisiyou

k3,k4应互质。若k3=t*k5,k4=t*k6,（k5、k6互质），则DB=k5*(t*a)+k6*(t*b),即构件看成长t*a，宽t*b,如DB=2a+2b情况

aimisiyou

理想状态，a,b各自倍增后差值为它们的最大公约数。这就是前面我说的（a,b）=（10,7）变为（21,20）的原因。（350,300）它们的差值刚好为它们的最大公约数50.目的也是为了提高材料的利用率。

aimisiyou

谁能写个函数（f  k1  k2  a  b）做出上面的矩形图形？显然（f  t*k1  t*k2  a  b）=(f  k1  k2  t*a  t*b).
(f 5 4 10 9)?

aimisiyou

虽然不知道具体图形怎样，但我可以肯定(k1*a+k2*b)*(k2*a+k1*b)的母板上可以裁出(k1+k2)^2个构件！

aimisiyou

所以可以先做个类似九九乘法表，f(1,1),f(1,2),f(1,3)……f(2,3),f(2,5)……f(3,4),f(3,5)……就转化为类似背包问题。

aimisiyou

当a-b=(a,b)的最大公约数时，矩形中的空隙均为正方形。所以当a=t*b时，可以考虑（a,(t-1)*b）情形。否则，图形类似以下

st788796

佩服楼主的钻研精神，期待好的结果出现！

aimisiyou

st788796 发表于 2016-5-4 11:16
佩服楼主的钻研精神，期待好的结果出现！

我只是对算法研究感兴趣，程序作图方面远远不及。不知你能否实现（f k1  k2  a b）作图程序？

ynhh

知道下多少块
不容易啊
但不知道画图
如何下啊

aimisiyou

ynhh 发表于 2016-5-4 16:53
知道下多少块
不容易啊
但不知道画图

我觉有时过程比结果更重要！当然具体的图形可以通过程序运算得到，类似找幻方一样只是运算量很大。k1,k2数值比较小的我能找到几个。