遞歸搜索 nyoj 325 nyoj 32

#include
#include
#include
using namespace std;
int n, r,ans[100];
void dfs(int u,int step)
{
	if (u <= 0)return;
	if (step == r)
	{
		for (int i = 1; i < r; i++)
			printf(%d, ans[i]);
		printf(%d
,u);
		return;
	}
	else
	{
		ans[step] = u;
		for (int i = 1;i<=n;i++)
		dfs(u - i, step + 1);
	}
}
int main()
{
	while (~scanf(%d%d, &n, &r))
	{
		for (int i = n; i >= r; i--)
		{
			dfs(i,1);
		}
	}
	return 0;
}

組合數

描述

找出從自然數1、2、... 、n（0

輸入

輸入n、r。

輸出

按特定順序輸出所有組合。
特定順序：每一個組合中的值從大到小排列，組合之間按逆字典序排列。

樣例輸入

5 3

樣例輸出

543
542
541
532
531
521
432
431
421
321

來源

[苗棟棟]原創

上傳者

苗棟棟

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
int n,a[1000],sum,ans;
void dfs(int u,int pos)
{
	ans = min(ans, abs(sum - 2*u));
	if (pos == n)return;
	dfs(u + a[pos], pos + 1);
	dfs(u, pos + 1);
	
}
int main()
{
	while (~scanf(%d, &n))
	{
		ans = inf;
		sum = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf(%d, a + i);
			sum += a[i];
		}
		dfs(0,1);
		printf(%d
, ans);
	}
	return 0;
}

zb的生日

時間限制：3000 ms | 內存限制：65535 KB 難度：2

描述

今天是陰歷七月初五，acm隊員zb的生日。zb正在和C小加、never在武漢集訓。他想給這兩位兄弟買點什麼慶祝生日，經過調查，zb發現C小加和never都很喜歡吃西瓜，而且一吃就是一堆的那種，zb立刻下定決心買了一堆西瓜。當他准備把西瓜送給C小加和never的時候，遇到了一個難題，never和C小加不在一塊住，只能把西瓜分成兩堆給他們，為了對每個人都公平，他想讓兩堆的重量之差最小。每個西瓜的重量已知，你能幫幫他麼？

輸入

多組測試數據（<=1500）。數據以EOF結尾
第一行輸入西瓜數量N (1 ≤ N ≤ 20)
第二行有N個數，W1, …, Wn (1 ≤ Wi ≤ 10000)分別代表每個西瓜的重量

輸出

輸出分成兩堆後的質量差

樣例輸入

5
5 8 13 27 14

樣例輸出

3

來源

ural

上傳者

李文鑫

這一題可以使用0-1背包來做，也可以遞歸的建一個搜索二叉樹，遞歸搜索的時間復雜度為2^n。