合版印刷拼版算法问题
所谓的合版印刷，就是我们会将来自不同客户、不同订单的卡片，拼版到同一个版面，然后制版印刷。
在合版印刷中，需要解决如下的问题。
一、矩形拼版算法
将若干尺寸不尽相同的小尺寸矩形拼版（排版）到一个大的矩形里。怎么样使得能够排版的小矩形更多？（版面的利用率更高？）
在排版中，还需要 注意一些约束条件，最主要的一个是：要能便于印后的裁切（一刀切）。所谓的一刀切，即指每一刀下去，都是一分为二。
如果小矩形都是同样的尺寸，这种拼版比较方便。主要是多尺寸矩形拼版。
目前我们通过遗传算法计算多尺寸拼版，但是经常得不到理想的结果，有时候甚至不如人工拼版的利用率。
并且，时间不太受控。
二、如何得到最好的拼版（花最少得钱，干同样多的活）
假如我们得到了一个拼版，我们可能会印刷200份、500份、1000份、2000份、5000份、10000份。（除非特殊情况，我们都是按这些数量印刷的）。
一般来说，印刷份数越多，则单份相对更便宜。 比如印200份共400元，而印500份只需要800元（而非1000元），公司有个价格表。
| 数量 | 200 | 500 | 1000 | 2000 | 5000 | 10000 |
|---|---|---|---|---|---|---|
| 价格 | 400 | 800 | 1550 | 3000 | 7000 | 12000 |
| 那么问题来了。假如某个订单有10款卡片，每款10000张。 我们会怎么印刷呢？ 理论上，如果还别很多别的订单卡片，如果也是每款10000张，这些卡片正好 | ||||||
| 能凑满一张版面。 那么情况就比较理想了。 然后还会有一些情况，比如假如别的订单卡片都是每款才5000张（甚至有些还不到5000张）。 那我这个订单 | ||||||
| 则很显然不合适印10000份。因为他们占不满一整张版面，浪费的会很多。假如200份400元。而4个订单平均占了这个版面，那每个订单的成本就是 | ||||||
| 400/4=100元。而这一个订单因为没有和别的订单共享版面，切浪费的空间很多，就会成本过高。 此时，我们可能会将这10款卡片每款10000张，变成 | ||||||
| 20款卡片每款5000张，也可能是50款卡片，每款2000张。 更甚至会有10款拆开，变成比如16款5000张（别的订单正好和这16款组成一个利用率很高的版面）和20款每款1000张的情况。 |
如何拼版更便宜？
假如某个卡片要15600张，我们可能最后是10000A+5000B+2000C+1000D+500E+200F的组合。（A,B，C，D，E，F指的款数，如果总的卡片数不少于原来的15600张即可），这里
可以按背包问题的解法。
求算法，有偿，谢谢。
标签：5000,印刷,卡片,订单,算法,每款,合版,拼版 From： https://www.cnblogs.com/YFree/p/18302128