《编程之美》读书笔记：电梯调度算法

最近在学习《 编程之美 》这本书，书中提到了很多很经典的算法问题和实现，学起来真是耗费脑细胞啊。书中的算法实现使用C编写的，这里作者自己写了一部分java的实现，如果有错误，还请各位读者批评指正。截图版权属于原作者。
github：

https://github.com/cstriker1407/think_in_java

1.8小飞的电梯调度算法

生成测试数据：

	Random random = new Random();
		
	int floorNums = random.nextInt(10) + 1;
	System.out.println("电梯总层数：" + (floorNums));
	int[] peopleNums = new int[floorNums];
	for (int i = 0; i < peopleNums.length; i++)
	{
		peopleNums[i] = random.nextInt(20);
		System.out.println("第[" + (i+1) +"]层的乘客数目为：" + peopleNums[i]);
	}

解法1：

	public static void liftDispatchA(int [] peopleNums)
	{
		int floorNum = peopleNums.length;
		
		int minUse = -1;
		int bestFloor = -1;
		
		for (int i = 0; i < floorNum; i++)
		{
			int thisUse = 0;
			/* i 代表当前停留楼层（从0计数） */
			for (int j = 0; j < floorNum; j++)
			{
				thisUse += Math.abs(i - j) * peopleNums[j];
			}
			if (minUse == -1 || minUse > thisUse)
			{
				minUse = thisUse;
				bestFloor = i;
			}
		}
		
		System.out.println("最优停留楼层：" + (bestFloor + 1));
		System.out.println("耗费人力：" + minUse);
	}

 解法2：

	public static void liftDispatchB(int [] peopleNums)
	{	
		int floorNum = peopleNums.length;
		
		/* 以电梯停留在第0层开始（从0计数） */
		int N1 = 0;
		int N2 = peopleNums[0];
		int N3 = 0;
		int minUse = 0;
		int bestFloor = 0;
		for (int i = 1; i < floorNum; i++)
		{
			N3 += peopleNums[i];
			minUse += peopleNums[i] * i;
		}
		
		/*
		 * F(i+1) = F(i) + N1 + N2 - N3
		 * 如果N1 + N2 > N3，则可以推出 F(i+1) > F(i)；
		 * 同时由于从电梯0层开始向上计数，因此N1增加，N3减小，一旦在某一层上N1 + N2 > N3，那么剩余的电梯层必然也会N1 + N2 > N3，
		 * 就可以不用计算了
		 */
		for (int i = 1; i < floorNum; i++)
		{
			if (N1 + N2 > N3)
			{
				break;
			}else 
			{
				bestFloor = i;
				minUse = minUse + N1 + N2 - N3;
				N1 += N2;
				N2 = peopleNums[i];
				N3 -= peopleNums[i];
			}
		}
		
		System.out.println("最优停留楼层：" + (bestFloor + 1));
		System.out.println("耗费人力：" + minUse);
	}