模型与算法四道题及“跳棋”思考题
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有两种状态，装入背包或者不装入背包。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枚棋子，仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。
