【51Nod】1268 - 和为K的组合（01背包 || bfs）

FishWang

发布于 2025-08-27 10:12:25

14100

代码可运行

运行总次数：0

代码可运行

点击打开题目

1268 和为K的组合

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

给出N个正整数组成的数组A，求能否从中选出若干个，使他们的和为K。如果可以，输出："Yes"，否则输出"No"。

Input

第1行：2个数N, K, N为数组的长度, K为需要判断的和(2 <= N <= 20，1 <= K <= 10^9)
第2 - N + 1行：每行1个数，对应数组的元素A[i] (1 <= A[i] <= 10^6)

Output

如果可以，输出："Yes"，否则输出"No"。

Input示例

Output示例

No

这道题k的范围给的特别大，但是仔细观察，num的范围只有10^6，n最多20，那么k最大也不过2*10^7，所以可以用01背包去做。

还有一种就是用bfs去做，之前用一个变量sum记录总和先预判一下。

代码如下：（01背包）

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int dp[20000005];
int main()
{
	int n;
	int num[22];
	int k;
	int sum = 0;
	scanf ("%d %d",&n,&k);
	for (int i = 1 ; i <= n ; i++)
	{
		scanf ("%d",&num[i]);
		sum += num[i];
	}
	if (sum < k)
		printf ("No\n");
	else if (sum == k)
		printf ("Yes\n");
	else
	{
		for (int i = 1 ; i <= n ; i++)
		{
			for (int j = k ; j >= num[i] ; j--)
				dp[j] = max(dp[j] , dp[j-num[i]] + num[i]);
		}
		if (dp[k] == k)
			printf ("Yes\n");
		else
			printf ("No\n");
	}
	return 0;
}

代码如下：（bfs）

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
bool ans;
int num[22];
int n;
int k;
void bfs(int pos , int sum)
{
	if (ans)		//有结果了直接退出 
		return;
	if (sum == k)
	{
		ans = true;
		return;
	}
	if (pos == n+1)		//搜索到结尾 
		return;
	bfs(pos+1 , sum + num[pos]);		//加上该点的值 
	bfs(pos+1 , sum);		//不加该点的值 
}
int main()
{
	int sum = 0;
	scanf ("%d %d",&n,&k);
	for (int i = 1 ; i <= n ; i++)
	{
		scanf ("%d",&num[i]);
		sum += num[i];
	}
	if (sum < k)
		printf ("No\n");
	else if (sum == k)
		printf ("Yes\n");
	else
	{
		ans = false;
		bfs(1,0);
		if (ans)
			printf ("Yes\n");
		else
			printf ("No\n");
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

数组