欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 1011 深度优先搜索 Sticks

程序员文章站 2022-03-16 10:57:38
...

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

有若干根相同长度的木棍,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;
}

 

相关标签: d do