poj 1011 深度优先搜索 Sticks

深度优先搜索的经典例题：

有若干根相同长度的木棍，George随机地将它们砍成N个部分，现在他想把N个小木棍拼回原来的木棍，但是他忘了原来木棍的长度L。请设计一个程序，找出最小的可能的原始木棍长度L。

分析：

（1）为什么不用动态规划而是要用深度优先搜索？

        原因1： 求解目标不同。动态规划和深度优先搜索的共同点是都是处理多个阶段的决策问题，但是动态规划是寻求最优解，而本题中，一旦设置原始木棍长度L为某个具体的值，我们的目标是判断：能用小木棍拼出长度L的木棍 or 不能用小木棍拼出长度L的木棍 ？

        原因2：适用条件不同。在动态规划中，容易被忽视的一个前提条件：每一步的决策对后面的决策没有直接影响，又称”无后效性“，在本题中，如果选中了第一根小木棍，那么后面的所有决策都不能再使用第一根小木棍了，因此具有”后效性“，不能用动态规划。

（2）为什么不用广度优先搜索？

        从理论上说，深度优先能解决的问题，广度优先也能解决，但是时间复杂度不一样，如果小棍的数量比较多，用广度优先搜索的搜索空间太大，会导致 Time Limit Exceeded

（3）有哪些剪枝

3.1 小木棍长度从大到小排序，每一次都优先挑长度最长的小木棍，可以快速压缩搜索空间，从而加速搜索过程；

3.2 规律1： 原始木棍长度L必须是小木棍总长度sum_len的约数；

3.3 对于若干根相同长度的小木棍，只要第一根小木棍不能用于拼出所有木棍，其余的小木棍全部可以 pass 掉！

3.4 对于一根待拼的新木棍，如果它的第一根小木棍不能用于拼出所有木棍，即使后面能拼出这一根新木棍，后面的新木棍同样不能用，因此可以确定地说，这个方案失败，直接返回 false。

代码：

/*
*  时间：0 ms
*  空间：260 KB
*  版权所有，转载务必注明出处。
*/
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

inline bool compare(int a, int b)
{
	return a > b;
}

int * a; int n; // #Sticks parts
bool * visit;   // 标记是否已经被访问过
int init_len;   // 原始木棍的长度
int sum_len;    // 所有小木棍的长度之和
int sample = -1;

// dfs
// 1. 为了更快的搜索，把所有小木棍排序，最长的放在第一个
// 表示当前搜索状态：（已经拼好的木棍数量 num, 剩余需要拼的木棍长度 res_len, 搜索的第一根小木棍的编号 start_id )
bool dfs(int num, int res_len, int start_id)
{
	// 判断当前状态
	if (res_len == 0) // 已经拼好一根了
	{
		// 全部拼好了
		if ( init_len * (num+1) == sum_len )
			return true;
		// 新开一根来拼
		return dfs(num + 1, init_len, 0);
	}

	// 找可以用的小木棍
	sample = -1;
	for (int i = start_id; i < n; i++)
	{
		if (a[i] <= res_len && false == visit[i] && a[i] != sample ) // 找到了&& 可用
		{
			visit[i] = true; // mark
			if (false == dfs(num, res_len - a[i], i + 1)) // 这一根不行
			{
				// 回溯
				visit[i] = false;
				sample = a[i];
			}
			else // 成功了
				return true;
			if (res_len == init_len)
				break;
		}
		
	}
	// 找不到可以用的小木棍
	return false;
}

int main(int argc, char* argv[])
{
	int i, j, k;
	while (scanf("%d", &n) && n)
	{
		// debugging code
		//n = 64;

		init_len = 0;
		sum_len = 0;
		bool solved = false;
		a = new int[n]; visit = new bool[n];
		memset(a, 0, sizeof(int)*n );
		memset(visit, 0, sizeof(bool)*n );
		for (i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
			// debugging code !
			//a[i] = 40;
		}
		// debugging code
		/*a[0] = 4;
		a[1] = 10;
		a[2] = 41;
		a[3] = 42;
		a[4] = 42;
		a[5] = 43;*/
		for (i = 0; i < n;i++)
			sum_len += a[i];

		// 预处理：对 a[i] 进行从大到小的排序
		sort(a, a + n, compare);
		int max_len = a[0];

		// 
		for (init_len = max_len; init_len <= (sum_len / 2); init_len++)
		{
			// 剪枝1： init_len 是 sum_len 的约数
			if ( sum_len % init_len != 0 )
				continue;

			if (dfs(0, init_len, 0))
			{
				solved = true;
				cout << init_len << endl;
				break;
			}
		}
		if (false == solved)
			cout << sum_len << endl;

		// 防止内存泄漏
		delete a;
	}
	return 0;
}