算法实验4《回溯法》

1. 编写一个简单的程序，解决8皇后问题。

#include

using namespace std;

bool backtrack(int list[8], int t)

{

if (t >= 8)return true;

for (int i = 0; i < 8; i++)

{

list[t] = i;

bool place = true;

for (int j = 0; j < t; j++)if (list[j] == i || j-t==list[j]-i || j-t==i-list[j])place = false;

if (place && backtrack(list, t+1))return true;

continue;

}

return false;

}

int main()

{

int list[8];

for (int i = 0; i < 8; i++)list[i] = 0;

backtrack(list, 0);

for (int i = 0; i < 8; i++)cout << list[i] << " ";

system("pause>nul");

return 0;

}

1）作业数 2）每个作业完成时间表：

作业完成时间

机器1

机器2

作业1

2

1

作业2

3

1

作业3

2

3

要求输出： 1）最佳完成时间 2）最佳调度方案

提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。

#include

using namespace std;

void backtrack(int *t1, int *t2, int *list1, int *list2, int *list, int &sumTime, int &time, int t, int n)

{

if (t >= n)

{

if (sumTime > time)sumTime = time;

return;

}

for (int i = 0; i < n; i++) //选择1个作业

{

bool place = true;

for (int j = 0; j < t; j++)if (list[j] == i)place = false; //判断这个作业是否可选

if (!place)continue;

list[t] = i;

if (t)t1[t] = t1[t - 1];

else t1[t] = 0;

t1[t] += list1[i];

if (t)t2[t] = (t1[t]>t2[t - 1]) ? t1[t] : t2[t - 1]; //这3行计算t2[i]

else t2[t] = t1[t];

t2[t] += list2[i];

time += t2[t];

if (time <= sumTime)backtrack(t1, t2, list1, list2, list, sumTime, time, t + 1, n);

time -= t2[t];

}

}

int main()

{

int n;

cin >> n;

int *list1 = new int[n]; //作业在机器1上运行的时间t11-t1n

int *list2 = new int[n]; //作业在机器2上运行的时间t21-t2n

int *t1 = new int[n]; //作业在机器1上完成的时间F11-F1n

int *t2 = new int[n]; //作业在机器2上完成的时间F21-F2n

int sumTime = 0; //总时间上界

for (int i = 0; i < n; i++)

{

cin >> list1[i] >> list2[i];

sumTime += (list1[i] + list2[i])*(i + 1);

}

int *list = new int[n]; //记录作业运行的顺序

int time = 0; //总时间

backtrack(t1, t2, list1, list2, list, sumTime, time, 0, n);

cout << sumTime << endl;

system("pause>nul");

return 0;

}

3. 数字全排列问题

任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。

注意：数字不能重复，N由键盘输入（N<=9）。

#include

using namespace std;

void backtrack(int n,int t,int *list)

{

if (t >= n)

{

for (int i = 0; i < n; i++)cout << list[i]+1 << " ";

cout << endl;

}

for (int i = 0; i < n; i++)

{

bool flag = true;

for (int j = 0; j < t; j++)if (list[j] == i)flag = false;

if (flag)

{

list[t] = i;

backtrack(n, t + 1, list);

}

}

}

int main()

{

int n;

cin >> n;

int list[9];

backtrack(n, 0, list);

system("pause>nul");

return 0;

}

MapReduce

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。