模型与算法四道题及“跳棋”思考题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<stdio.h>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<k;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有两种状态，装入背包或者不装入背包。

X i=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(v j)=w1j，否则T(v j)=+∞。

Step3：在所有T标号中选取最小的，将其改为P标号，并重新计算有T标号的其它各点的T标号。

Step4：转step3，直至所有的顶点得到P标号为止。

Step5：算法结束。

5、独立砖石跳棋问题题目：图中33个顶点摆着32枚棋子，仅中央的顶点空着未摆放棋子。

下棋的规则是任一棋子可以沿水平或垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。

试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。

解：回溯法的基本思想是：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树，算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解，如果肯定不包含，跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

简而言之就是从某一可行解开始进行，能进则进，不进则退至上一步，换一可行路径再试。

本题中用回溯的思想，如果两个子之间能跳，那么跳了之后记录其新的位置，因为跳的前后都是一个问题，所以我们能用递归分治，跳了一次之后棋子数减一，并把跳过的棋子和编号最后的棋子交换，这样就达到了把棋子去掉的目的，并把最优解保存。

把棋盘上的位置规定成一个二维数组，如图所示：#include <iostream>#include <fstream>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] = '.';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;default:break;}return 0;}//主函数void main(){answer.txt // 输出一个解到文本文件ofstream answer("answer.txt");Init_diamond();top = nx = ny = ndir = 0;while(1) // 回溯遍历，直到找到一个解{if(Left_diamond == 1 && diamond[3][3] == '*'){ break; }for(y=ny; y<7; y++,nx=0){for(x=nx; x<7; x++,ndir=0){for(int dir=ndir; dir<4; dir++){if(Move_diamond(y, x, dir)){Left_diamond--;nx = ny = ndir = 0;goto nextstep;}}}}nextstep:if(y == 7){top--;if(top >= 0) // 回到上一步，并改变方向{last_step = mystack[top];diamond[(last_step.sy + last_step.ty)/2][(last_step.sx + last_step.tx)/2] = '*'; diamond[last_step.sy][last_step.sx] = '*';diamond[last_step.ty][last_step.tx] = '.';nx = last_step.sx;ny = last_step.sy;ndir = last_step.dir + 1;Left_diamond++;}else{answer<<"Can't find any answer, I am sorry."<<endl;cout<<"Can't find any answer, I am sorry."<<endl;flag=0;break;}}}Init_diamond();answer<<"The initialization diamond states:"<<endl;for(int i=0; i<7; i++){for(int j=0; j<7; j++){ answer<<diamond[i][j]<<' '; }answer<<endl;}answer<<endl<<endl; for(int n=0; n<top; n++) // 输出解{answer<<"step "<<n+1<<": Move diamond ("<<mystack[n].sy+1<<","<<mystack[n].sx+1<<")--->("<<mystack[n].ty+1<<","<<mystack[n].tx+1<<")"<<endl;diamond[mystack[n].sy][mystack[n].sx] = '.';diamond[(mystack[n].sy+mystack[n].ty)/2][(mystack[n].sx+mystack[n].tx)/2] = '.'; diamond[mystack[n].ty][mystack[n].tx] = '*';answer<<"Left diamonds : "<<top-n<<endl;for(int k=0; k<7; k++){for(int j=0; j<7; j++){ answer<<diamond[k][j]<<' '; }answer<<endl;}answer<<endl<<endl;}if(flag){cout<<"The answer has been exported to file \"answer.txt\" in the same directory.Welcome to see!"<<endl;}}。