算法实验4《回溯法》

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

#include<iostream>
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）最佳调度方案 提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。

#include<iostream>
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<iostream>
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;
}