资源描述：
《数学模型经典题目及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、模型与算法四道题及“跳棋”思考题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.S
2、4:输出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未
3、si≥fj∀j∈S已}是否为空集，若A为空集，则此机器已经满了，k=k+1，S已=∅，进入S4；否则从A中选出一个开始时间最小的任务i，并输出：“任务i分配到第k个机器“，并S已=S已∪{i}，S未=S未-{i}，进入S3。S4：
4、判断S未是否为空集，若是，程序结束；否则进入S3。#includevoidmain(){chara[7]={'a','b','c','d','e','f','g'};charb;charx[7];ints[7]={0,3,4,9,7,1,6};intf[8]={2,7,7,11,10,5,8,0};inti,j,k,n,m,c,d,x1,x2,x3,x4;booly1,y2;k=0;m=1;for(i=0;i<7;i++)//将任务按开始时间从小到大排序。{for(j=i;j<7;j++){if(s[i]
5、>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=f[n]))//保证即将安排的任
6、务开始时间不得小于前一个任务的结束时间。{k=k+1;x[k]=i;n=x[k];printf("%c",a[i]);}}if(i==6)n=8;}printf("");++m;}while(k<6);}3、0—1背包问题启发式算法（回溯法）：给定n中物品和一个背包，假设物品i的重量wi，其价值为vi，背包容量为C。物品i有两种状态，装入背包或者不装入背包。Xi=0时表示物品i不装入背包，Xi=1时表示物品装入背包，则决策物品是否装入背包的问题转化为一个二叉树搜索问题，根据约束条件进行剪枝，然后结合回溯法求出解。所给物
7、品按照单位价值量进行非增排序，解空间表示为集合S={X1，X2，…..Xn
8、Xi∈0,1，i=1,2….n}，如何选择物品装入背包，使得包内物品的总价值最大的算法如下：Step1：从根节点开始，计算此时背包的剩余容量和背包中物品的价值；此时根节点为活结点，也是当前的扩展结点。Step2：以深度优先方式搜索，从当前的一个扩展结点向纵深方向移至一个新的结点，此时这根结点成为活结点并成为当前扩展结点。计算此时背包的剩余容量，并计算背包中物品的价值；Step3：根据约束条件判断当前的扩展结点是否可以再向纵深方向移动；Step4：如
9、果满足约束条件则向纵深方向移至新节点，否则回溯至最近的活结点，使其成为当前扩展结点；Step5：转step2，直到找出最优解或者解空间中没有活结点；Step6：算法结束。0—1背包问题的邻域搜索算法：Step1：根据约束条件给出一个可行解S0，并计算初始可行解时装入背包中物品的价值V0；Step2：利用贪心算法构造领域函数，将单位价值量大的物品替换初始可行解中的单位价值量小的物品；Step3：计算新解S1时，背包中物品的价值V1，若V1>V0，则S0=S1，V0=V1；Step4：转Step1，直到算出最优解或者满意解为止
10、；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
