最優化排版問題

王子般的懒人

假如要在A4紙上打印不同數量的撲克牌：

紅心A——100張
黑桃A——80張
方塊A——200張
梅花A——150張

A4紙的規格為：210*297mm
撲克牌的規格為：7*9mm

要求最優化排版，打印以上四種不同數量的撲克牌A，問需求A4紙的最少數量是多少？
有一個條件：排版時因某種原因，每兩個撲克牌之間必須要留至少3mm，且排版時至少有2mm不能排到A4紙的邊緣.

請高手幫忙解答。

gxqcn

这个确实比较难。
我说个我自己的真实案例。

三年前，我给自己的房子装修，由于是顶层又靠西面，所以决定给所有的玻璃（有70多块）贴隔热膜。
我仔细测量了一下玻璃尺寸，用Excel保存起来。
而后算面积总和，再加一点余量，然后到网上订货。
隔热膜宽度是5英尺（1.524米），长度则由用户决定，按面积算钱。

我的作法是：
1、尽量拼凑，看哪几块在尺寸上接近1.52米；
2、优先解决尺寸的玻璃，小尺寸的玻璃则可由边角料解决。
最后，非常完美地完成了任务（其中，在统计时少算了4块玻璃，余量大幅下降，最后也完成了，且每块玻璃上帖的都是完整的膜）。

在纸上排布剪裁法，确实比较伤脑筋，而且要求下刀要少，剪裁方便。
我曾想在网上搜索相关软件，但未果。

楼主的问题相对来说要比上面的简单一点。因为需要考虑的尺寸种类不多。

王子般的懒人

因平時工作中遇到的不只是以上的，還有可能會出現更多同規格但不同數量的排版問題，不知道是否有比較方便的辦法來算出最少的紙張用量。因為涉及生產上的成本問題，希望高手出手相助！

hujunhua

等离子切割机（用于钢板下料）的驱动程序里有下料排版优化功能，但是我没有研究过内核。
工厂的钢板下料件形状和尺寸千奇百怪（以圆形、环形、弓形和多边形居多），内中的排版优化程序肯定不简单。

mathe

不同花色的牌大小相同，那么对于排版就没有区别了

hujunhua

王子般的懒人

5# mathe


有區別，因每個花色的數量不同，要從最少量使用A4紙上考慮

wayne

8# 王子般的懒人
没区别吧。
先计算得到总共需要多少张扑克牌。
然后根据花色按比例分配到各种花色就行了

王子般的懒人

9# wayne


如果有很多個花要打印的話，按比例不一定在同一張紙上擺滿所有花色，有可能數量少的花色會不用排在其中幾張紙上的.

王子般的懒人

9# wayne


還想補充一點是：如果第一張排版確定，假定需要10張A4紙，則其它9張紙都是按同樣的排版打印。所以會出現有部分花色會多打印的情況，這種情況可以接受，最主要目的是所需的A4紙數量最少。