2.3 构造法模拟的实验范例
构造法模拟需要完整、精确地构造出反映问题本质的数学模型，根据该模型设计状态变化的参数，计算模拟结果。由于数学模型建立了客观事物间准确的运算关系，因此其效率一般比较高。
构造法模拟的关键是找到数学模型。问题是，能产生正确结果的数学模型并不是唯一的，从不同的思维角度看问题，可以得出不同的数学模型，而模拟效率和编程复杂度往往因数学模型而异。即便有数学模型，解该模型的准确方法是否有现成算法、编程复杂度如何，这些问题也需要我们仔细考虑。
【2.3.1 Packets】
【问题描述】
一家工厂生产的产品被包装在一个正方形的包装盒中，产品具有相同的高度h，大小规格为11、22、33、44、55和66。这些产品是用和产品具有相同高度h，大小规格为6*6的正方形邮包交付给客户的。由于费用问题，工厂和客户都要使将订购的物品从工厂发送给客户的邮包的数量最小化。请编写一个程序，对于按照订单发送给定的产品，找出最少的邮包数量，以节省费用。
输入：
输入由若干行组成，每行描述一份订单，每份订单由6个整数组成，整数之间用一个空格分开，连续的整数表示从最小的11到最大的66每种大小的包装盒的数量，输入以包含6个0的一行结束。
输出：
对每行输入，输出一行，给出邮包的最小数量。对于输入的最后一行“空输入”没有输出。
试题来源：ACM Central Europe 1996
在线测试地址：POJ 1017，ZOJ 1307，UVA 311
试题解析
这是一道构造法模拟题，其使用的数学模型是一个贪心策略——按照尺寸递减的顺序装入包装盒。由于邮包的尺寸为66，因此每个44、55和 66 的包装盒需要一个单独的邮包。
6*6：刚好。
55：放入66 的邮包中，剩下的用1*1填充。
44：放入66的邮包后,先用22填充, 没有22的就用1*1填充。
33：一个66的邮包可以放4个。
22和11一样操作。
具体实现方法如下。设i*i的包装盒数为ai(1≤i≤6)：
放入66、55、44、33的包装盒至少需要邮包数M=a6+a5+a4+a34。
M个邮包可填入22的包装盒数L2=a45+u［a3 mod 4］u［0］=0，u［1］=5，u［2］=3，u［3］=1。若有剩余（a2>L2），则放入新增的a2－L29个邮包，即M+=a2－L29。
最后使用11的L1（=m36-a636-a525-a416-a39-a2*4）个包装盒填满M个邮包。若有剩余（a1>L1），则放入新增的a1－L136个邮包，即M+=a1－L136。
显然，M是放入所有包装盒的最少邮包数。
程序清单
#include <iostream>
using namespace std;
int main()
{
int a［10］,i,j,sum,m,left1,left2;// 每种尺寸的包装盒数为a［］；包装盒总数为sum；使用的邮包数为m；当前
// 邮包可装入2*2的包装盒数为left2，可装入1*1的包装盒数为left1
int u［4］={0,5,3,1};// u［a［3］% 4］
while (1)
{
sum=0;
for(i=1;i<=6;i++)// 输入每种尺寸的包装盒数量，累计包装盒的总数
{
cin>>a［i］;
sum+=a［i］;
}
if(sum==0) break;// 若输入6个0，则退出程序
m=a［6］+a［5］+a［4］+(3+a［3］)/4;// 计算放入前4种大尺寸的包装盒至少需要的邮包数
left2=a［4］*5+u［a［3］%4］;// 计算M个邮包可填入2*2的包装盒数
if(a［2］>left2)// 若2*2的包装盒有剩余，则累计新增的邮包
m+=(a［2］-left2+8)/9;
left1=m*36-a［6］*36-a［5］*25-a［4］*16-a［3］*9-a［2］*4;
// 填满上述邮包需要使用1*1的
// 包装盒数
if(a［1］>left1)// 若1*1的包装盒有剩余，则累计新增的邮包
m+=(a［1］-left1+35)/36;
cout<<m<<endl;// 输出最少邮包数
}
return 0;
}
【2.3.2 Paper Cutting】
【问题描述】
ACM经理需要用名片将他们自己介绍给客户和合作伙伴。名片上的信息印刷到一大张纸上之后，要用一台特殊的切割机来切割纸张。由于机器的操作花费非常昂贵，因此要尽量减少切割的次数。请编写程序，找到切割产生名片的最佳解决方案。
切割有若干条必须遵守的限制。要以恰好a*b张名片的网格结构印刷名片。由于印刷软件的限制，结构的尺寸（在一行和列中名片的数量）是固定的，不能改变。纸张是矩形的，它的大小是固定的。网格必须垂直于纸张的边，也就是说，它只可以进行90°的旋转。但是，可以交换行和列的含义，卡片可以放置在纸张上的任何位置，卡片的边和纸张边可以重合。
例如，设定名片的大小是34厘米，网格大小为12张名片。图2.3-1给出网格的四个可能的方案。要求给出每种情况所需要的最小的纸张尺寸。
用于切割卡片的切割机能够进行任意长度的连续切割，切割能够贯穿整片的纸张，不会中途停止。一次切割只能针对一片纸张 —— 不能为了节省切割次数将纸张叠加起来切，也不能把纸张折叠起来切。
输入：
输入由若干测试用例组成，每个测试用例由在一行上的6个正整数A、B、C、D、E、F组成，整数间用一个空格分开，这些数的含义如下：
A和B是矩形网格的大小，1 ≤ A，B≤ 1000；C和D是卡片的尺寸，以厘米为单位，1 ≤ C，D ≤ 1000；E和F是纸张的尺寸，以厘米为单位，1 ≤E，F≤ 1000000。
输入以6个0的一行结束。
输出：
对每个测试用例，输出一行，该行给出“The minimum number of cuts is X.”，其中X是要求切割的最小次数。如果纸张不能符合卡片网格，则输出“The paper is too small.”来代替。
试题来源：CTU Open 2003
在线测试地址：POJ 1791，ZOJ 2160
试题解析
先在纸张中切网格，然后在网格内切名片。设矩形网格大小为ab、名片尺寸为cd、纸张尺寸为ef，即纵向有a张尺寸为c的名片,纵向总长为ac；横向有b张尺寸为d的名片,横向总长为bd。而名片的切割在纸张范围内进行，由此得出约束条件：（ac≤e）&&（b*d≤f）。
切出大小为ab的网格，至少需要ab-1次切割。若acdb-1+(ac1）网格大小为ba（转90°）、名片尺寸为cd(不变)、纸张尺寸为e*f（不变）。
2）网格大小为ab（不变）、名片尺寸为dc（转90°）、纸张尺寸为e*f（不变）。
3）网格大小为ba（转90°）、名片尺寸为dc（转90°）、纸张尺寸为e*f（不变）。
按照上述方法依次得出三种情况下的切割次数c1、c2、c3，如果其中任意一种情况不满足约束条件，则切割次数为∞。显然，最少切割次数为Ans=min{c0，c1，c2，c3}若Ans=∞，则说明纸张不能符合卡片网格，因为所有可能情况都不满足约束条件。
程序清单
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TOOBIG INT_MAX
int ncuts(int a,int b,int c,int d,int e,int f) ;
void do_solve(int a,int b,int c,int d,int e,int f) // 输入矩形网格大小、卡片尺寸和纸张的尺寸，枚举
// 旋转的4种情况，计算最小切割次数
{
int x,m ;
m=ncuts(a,b,c,d,e,f) ; // 计算未旋转的切割次数
if ((x=ncuts(b,a,c,d,e,f))<m) m=x ;// 网格转90°，调整最小切割次数
if ((x=ncuts(a,b,d,c,e,f))<m) m=x ;// 卡片转90°，调整最小切割次数
if ((x=ncuts(b,a,d,c,e,f))<m) m=x;// 网格和卡片各转90°，调整最小切割次数
if (m==TOOBIG)
puts("The paper is too small.");
else
printf("The minimum number of cuts is " "%d.＼n",m) ;
}
int ncuts(int a,int b,int c,int d,int e,int f)// 计算当前情况下（矩形网格大小为(a，b)、卡片尺寸
// 为(c，d)、纸张尺寸为（e，f））的最小切割次数
{
if (a*c>e || b*d>f) return TOOBIG ;// 若超出纸张范围，则返回∞
return a*b-1+(a*c<e)+(b*d<f);// 返回切割次数
}
int main()
{ int a,b,c,d,e,f ;
for(;;) {
a=0 ; b=0 ; c=0 ; d=0 ; e=0 ; f=0 ;
scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f) ;// 输入矩形网格大小、卡片尺寸和纸张的尺寸
if (!a && !b && !c && !d && !e && !f) break ;// 若全为0，则结束程序
do_solve(a,b,c,d,e,f) ;
}
return 0 ;
}
