【Day 16】Function - Practice 2

题目

此题题目指定使用的演算法为

输入输出格式

此题测资会给定机场选址数量airportQ (n)、各机场建造成本cost (c)、任两个机场间航线所创造的收益benefit (b)。

Sol.
先建立costArray, benefitArray, buildArray阵列，分别在阵列中存各机场建造成本、任两个机场间航线所创造的收益、是否兴建此机场（盖 = 1, 不盖 = 0 )。
宣告变数totalB，代表总利润。

由於演算法设定我们先预设 n 个机场都要盖，因此先宣告buildArray中各项皆为 0。

此题我所设的函数叫做tearDown，用来判断在这一轮中是否有要拆的机场

设nowB为目前已加总的利润、nowC为目前已加总的成本、MaxB为弱拆除其中一个机场所获最大利润、tear代表要拆除的机场，每跑进来一圈就要将tear初始化归 0。

Pseudocode

tearDown：{
for i in range airportQ    // 若拆除第i个机场
    if 这个机场要盖
		for j in range airportQ	// benefitArray[j][k] 的j
			if确定有要盖第j个机场且j != i
				nowC += 第j个机场的成本
				for k in range airportQ
					if确定有要盖第k个机场且k != i
						nowB += 第j个机场与第k个机场航线的利润
			nowB -= nowC
			nowC 归 0
// 这个else很重要，因为 nowB 一开始是 0，MaxB 一开始负很大，如果第 0 个机场不盖那下面就会遇到bug
	else
		continue

if nowB比现在已知的最大利润 MaxB 大 且 nowB 比跑进此函数进行下一轮前的总利润 totalB 大
		MaxB = nowB
		tear = i

return tear	// 若不能再拆则回传 -1
}

在main function中：
for i in range airportQ
	tear = tearDown(参数们)	// 呼叫函数
	if tear回传的值不为 -1    // 代表有可以拆的机场，就会进行下一轮
		for j in range airportQ
			for k in range airportQ
				if i == tear或 k == tear		// 注1*
					totalB -= benefitArray[j][k]
					benefitArray[j][k] = 0	// 将与要拆掉的机场有关联的航线利润都归0，注1
		totalB += cost[tear]	// 将要拆掉的机场成本加回来
		cost[tear] = 0	//将与要拆掉的机场之成本归0，注1
		将buildArray[tear] 归 0
	else
	break
最後输出答案：buildArray;totalB

注1
此题因为机场拆掉之後即不会再读取有关这个机场的资料，因此可以直接将costArray、benefitArray中的资料归 0，但是这个方法比较取巧，若题目会再用到已拆除的机场的资料、或再判读一次是否要兴建此机场，则注1* if的条件还需再判断j != k以及buildArray[j] == 1。