回溯法的遞歸與疊代版本

  以2019藍橋杯C/C++B組的兩個題目為例，來進行說明回溯法的遞歸和疊代版本

作為籃球隊教練，你需要從以下名單中選出 1 号位至 5 号位各一名球員，組成球隊的首發陣容。每位球員擔任 1 号位至 5 号位時的評分如下表所示。請你計算首發陣容 1号位至 5 号位的評分之和最大可能是多少？

  此處的遞歸和疊代都是用于周遊全部解空間尋找最優解，是以思路是差不多的，每個人每個位置都嘗試一下。但是這個嘗試的順序對于代碼的複雜度有很大的關系。我們應該固定站位資訊，每個位置的球員做循環，其實五層嵌套循環也能解決這個問題，但是那樣代碼就太不優雅了。

這裡歸納一下，回溯法遞歸與疊代方式之間轉換的通用方法：

1. 由于都是在二維向量中查找最優組合，是以我們以一個所有元素必須取值的軸作為外層的軸對象，在這道題目中，就是以位置作為這條軸，因為這個變量可以依次取值，到第5号位的時候，就可以計算結果了，直接利用這個條件能夠減少很多判斷條件。
2. 位置和球員之間的關系可以用一個一維數組表示，a[位置] = 球員，這樣在疊代回溯的過程中可以直接通過x[位置–]傳回上一個位置，x[位置]++來通路下一個球員，而且回溯的過程中，位置和球員的資訊被關聯到一起，使得可以進行下一次搜尋。
3. 要注意搜尋的條件，如這道題使用一維數組來記錄球員是否已經被選擇了，要注意回溯時相關條件的改變，比如sum之前增加過，回溯之後要把sum-前一個加上去的值。

 具體的改寫方式，見下列代碼。理論上都是可以改寫的。

C++代碼

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int a[20][6] = {{1,97,90,0,0,0},
                {2,92,85,96,0,0},
                {3,0,0,0,0,93},
                {4,0,0,0,80,86},
                {5,89,83,97,0,0},
                {6,82,86,0,0,0},
                {7,0,0,0,87,90},
                {8,0,97,96,0,0},
                {9,0,0,89,0,0},
                {10,95,99,0,0,0},
                {11,0,0,96,97,0},
                {12,0,0,0,93,98},
                {13,94,91,0,0,0},
                {14,0,83,87,0,0},
                {15,0,0,98,97,98},
                {16,0,0,0,93,86},
                {17,98,83,99,98,81},
                {18,93,87,92,96,98},
                {19,0,0,0,89,92},
                {20,0,99,96,95,81}};
int vis[21]; //20個隊員是否被通路過，放21是怕周遊的時候越界
int max_score = 0;

//index表明了遞歸的深度，也表明是哪個位置，sum是目前情況的總分
void DFS(int index, int sum)
{
	if(index == 6) //已經選了5個人，這是後可以記分了
	{
		max_score = max(max_score, sum);
		return;
	}
	for(int i=0; i<20; i++) //對于每一個隊員，每一個位置都嘗試一下
	{
		if(vis[i] == 0) //隻有這個隊員沒有被安排的時候才通路它
		{
			vis[i] = 1;
			DFS(index+1, sum+a[i][index]); //此時将該隊員的該位置的得分和已選擇了的做比較
			vis[i] = 0; //重新嘗試下一種情況
		}
	}
}


void DFS_Iterator()
{
	int k=1; //第一個站位
	int x[6] = {0}; //相應站位對應隊員
	int sum = 0;
	x[1] = -1;
	
	while(k > 0)  //控制站位數
	{
		x[k] += 1;
		while((x[k]<20) && vis[x[k]] == 1) //該隊員被征用了就設為1
			x[k]++; //隊員号提升一個
		sum += a[x[k]][k];
		vis[x[k]] = 1; //該隊員占據這個位置
		if(x[k]<20)  //隊員号不能越界
		{
			if(k == 5)
			{
				max_score = max(max_score,sum);
				sum -= a[x[k]][k];  //此處也需要減去剛剛的結果
				vis[x[k]] = 0;
			}
			else
			{
				k++; //向下一行掃描
				x[k] = -1; //下一個隊員又從位置0開始掃描
			}
		}else
		{
			k--;  //回到上一個位置的情況，由于x[k]裡面已經儲存了剛才隊員的資訊
			sum -= a[x[k]][k];  // 這裡減去的是上一行的資訊，因為上一行需要向前移動
			vis[x[k]] = 0;
		}
			
	}
}

int main()
{
    //DFS(1,0);
	DFS_Iterator();
    cout<<max_score;
	
	return 0;
}