数学模型经典题目及答案
- 格式：pdf
- 大小：275.71 KB
- 文档页数：11
数学模型经典题⽬及答案
模型与算法四道题及“跳棋”思考题1、找零钱
思想：先找零25分的，然后再依次满⾜10分、5、1.
算法：
符号说明：Sum1：消费⾦额。
Sleft2：找零⾦额。
X1、X2、X3、X4：需要找零25分、10分、5分和1分的数量。
S1：请输⼊⼩于100分的消费⾦额：Sum1。
S2：需要找零的⾦额为：Sleft2=100- Sum1。
S3：计算与赋值：X1=[Sleft2/25]、X2=[(Sleft2-25*X1)/10]、X3=[(Sleft2-25* X1-10*X2)/5]、X4=Sleft2-25*X1-10*X2-5*X3.
S4:输出X1、X2、X3、X4。
2、带有时间窗的任务分配
算法S
未
：还未被分配的任务集合。S
已
：已经被分配的任务集合。A：临时集合。
S1:赋值k=1。
S2：从S
未
中找出⼀个开始时间最⼩的任务i，并输出：“任务i分配到第k个机器“，并且 S
已=S
已∪{ i }，S
未=S
未{ i }。
S3：判断A={i∈S
未|s i≥f j? j∈S
已}是否为空集，若A为空集，则此机器已经满
了，k=k+1， S已=?，进⼊S4；否则从A中选出⼀个开始时间最⼩的任务i，并
输出：“任务i分配到第k个机器“，并S
已=S
已∪{ i }，S
未=S
未{ i }，进⼊S3。
S4：判断S
未
是否为空集，若是，程序结束；否则进⼊S3。
#include
void main()
{
char a[7]={'a','b','c','d','e','f','g'};
char b;
char x[7];
int s[7]={0,3,4,9,7,1,6};
int f[8]={2,7,7,11,10,5,8,0};
int i,j,k,n,m,c,d,x1,x2,x3,x4;
bool y1,y2;
k=0;
m=1;
for(i=0;i<7;i++) // 将任务按开始时间从⼩到⼤排序。{
for(j=i;j<7;j++)
{
if(s[i]>s[j])
{
c=s[i];
s[i]=s[j];
s[j]=c;
d=f[i];
f[i]=f[j];
f[j]=d;
b=a[i];
a[i]=a[j];
a[j]=b;
}
}
}
x[0]=0;
n=0;
do
{printf("安排在第%d台机器上的任务有：",m);
if(m==1) printf(" %c",a[0]);
for(i=1;i<7;i++)
{y2=1;
for(j=0;j
{y1=(i!=x[j])&&y2; // 保证即将安排的任务是未被分配的。
y2=y1;
}
if(y1)
{
if((s[i]>=f[n])) // 保证即将安排的任务开始时间不得⼩于前⼀个任务的结束时间。
{k=k+1;
x[k]=i;
n=x[k];
printf(" %c",a[i]);}
}
if(i==6) n=8;
}
printf("\n");
++m;}while(k<6);
}
3、0—1背包问题启发式算法（回溯法）：
给定n中物品和⼀个背包，假设物品i的重量w i，其价值为v i，背包容量为C。物品i有两种状态，装⼊背包或者不装⼊背包。Xi=0时表⽰物品i不装⼊背包，X i=1时表⽰物品装⼊背包，则决策物品是否装⼊背包的问题转化为⼀个⼆叉树搜索问题，根据约束条件进⾏剪枝，然后结合回溯法求出解。所给物品按照单位价值量进⾏⾮增排序，解空间表⽰为集合S={X1
，X2，…..X n|X i∈{0,1}，i=1,2….n}，如何选择物品装⼊背包，使得包内物品的总价值最⼤的算法如下：Step1：从根节点开始，计算此时背包的剩余容量和背包中物品的价值；此时根节点为活结点，也是当前的扩展结点。
Step2：以深度优先⽅式搜索，从当前的⼀个扩展结点向纵深⽅向移⾄⼀个新的结点，此时这根结点成为活结点并成为当前扩展结点。计算此时背包的剩余容量，
并计算背包中物品的价值；Step3：根据约束条件判断当前的扩展结点是否可以再向纵深⽅向移动；
Step4：如果满⾜约束条件则向纵深⽅向移⾄新节点，否则回溯⾄最近的活结点，使其成为当前扩展结点；
Step5：转step2，直到找出最优解或者解空间中没有活结点；
Step6：算法结束。
0—1背包问题的邻域搜索算法：
Step1：根据约束条件给出⼀个可⾏解S0，并计算初始可⾏解时装⼊背包中物品的价值V0；
Step2：利⽤贪⼼算法构造领域函数，将单位价值量⼤的物品替换初始可⾏解中的单位价值量⼩的物品；
Step3：计算新解S1时，背包中物品的价值V1，若V1>V0，则S0=S1，V0=V1；
Step4：转Step1，直到算出最优解或者满意解为⽌；
Step5：算法结束。
例⼦：假设n=6，i=1,2…..6，W={9,7,5,13,8,6}，V={4,3,2,5,3,2}，C=24;
利⽤邻域搜索算算法求解时：Step1：⾸先给出初始可⾏解S0={1,1,1,0,0,0}，此时V0=9;
Step2：通过邻域搜索⽤S1={1,1,0,0,1,0}替换S0。
Step3：计算V1=10，V1>V0，则S0=S1，V0=V1；
Step4：转Step1，直到算出最优解或者满意解为⽌；
Step5：算法结束。
4、写出⽹络图中寻找V1⾄Vn的路径的算法
Step1：⽤W ij表⽰图中两点V i与V j之间的距离，若V i与V j之间没有连线，W ij=+∞。显然可令图中每个顶点W ii=0。
Step2：给起点V i标上固定的标号P(v1)=0,并打上*号。给其它各点标上临时标号，如起点到该点有边直接相连，就标T(vj)=w1j，否则T(v j)=+∞。Step3：在所有T标号中选取最⼩的，将其改为P标号，并重新计算有T标号的其它各点的T标号。
Step4：转step3，直⾄所有的顶点得到P标号为⽌。
Step5：算法结束。
5、独⽴砖⽯跳棋问题
题⽬：图中33个顶点摆着32枚棋⼦，仅中央的顶点空着未摆放棋⼦。下棋的规则是任⼀棋⼦可以沿⽔平或垂直⽅向跳过与其相邻的棋⼦，进⼊空着的顶点并吃掉被跳过的棋⼦。试设计⼀个算法找出⼀种下棋⽅法，使得最终棋盘上只剩下⼀个棋⼦在棋盘中央。
解：回溯法的基本思想是：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树，算法搜索⾄解空间树的任意⼀点时，先判断该结点是否包含问题的解，如果肯定不包含，跳过对该结点为根的⼦树的搜索，逐层向其祖先结点回溯；否则，进⼊该⼦树，继续按深度优先策略搜索。简⽽⾔之就是从某⼀可⾏解开始进⾏，能进则进，不进则退⾄上⼀步，换⼀可⾏路径再试。
本题中⽤回溯的思想，如果两个⼦之间能跳，那么跳了之后记录其新的位置，因为跳的前后都是⼀个问题，所以我们能⽤递归分治，跳了⼀次之后棋⼦数减⼀，并把跳过的棋⼦和编号最后的棋⼦交换，这样就达到了把棋⼦去掉的⽬的，并把最优解保存。
把棋盘上的位置规定成⼀个⼆维数组，如图所⽰：#include
#include
using namespace std;
struct step //记录移动棋⼦的信息
{
int sx, sy; // 记录移动棋⼦前棋⼦的位置
int tx, ty; // 记录移动棋⼦后棋⼦的位置
int dir; // dir值代表移动棋⼦的⽅向
}
struct step mystack[100], last_step;
char diamond[7][7];
int Left_diamond = 32;
int x, y, nx, ny, ndir, top; //ndir值代表⽅向, 0向右, 1向下, 2向左, 3向上int flag=1; // 是否成功找到解的标志
//初始化棋盘
void Init_diamond()
{for(int i=0; i<7; i++)
{
for(int j=0; j<7; j++)
{
if((i<2 || i>4) && (j<2 || j>4));
else
{
diamond[i][j] = '*';
}
}
}
diamond[3][3] = '.';
}
//移动棋⼦
int Move_diamond(int y, int x, int dir)
{
if(diamond[y][x] != '*')
{ return 0; }
struct step temp;
switch(dir)
{
case 0:
{
if(x+2>6 || diamond[y][x+1]!='*' || diamond[y][x+2]!='.') { return 0; }
diamond[y][x] = diamond[y][x+1] = '.';
diamond[y][x+2] = '*';
temp.sx = x;
temp.sy = y;
temp.tx = x+2;
temp.ty = y;
temp.dir = dir;
mystack[top++] = temp;
return 1;
}
break;case 1:
{
if(y+2>6 || diamond[y+1][x]!='*' || diamond[y+2][x]!='.')
{ return 0; }
diamond[y][x] = diamond[y+1][x] = '.';
diamond[y+2][x] = '*';
temp.sx = x;
temp.sy = y;
temp.tx = x;
temp.ty = y+2;
temp.dir = dir;
mystack[top++] = temp;
return 1;
}
break;
case 2:
{
if(x-2<0 || diamond[y][x-1]!='*' || diamond[y][x-2]!='.')
{ return 0; }
diamond[y][x] = diamond[y][x-1] = '.';
diamond[y][x-2] = '*';
temp.sx = x;
temp.sy = y;
temp.tx = x-2;
temp.ty = y;
temp.dir = dir;
mystack[top++] = temp;
return 1;
}
break;
case 3:
{
if(y-2<0 || diamond[y-1][x]!='*' || diamond[y-2][x]!='.')
{ return 0; }
diamond[y][x] = diamond[y-1][x] = '.';
