[搜索][51nod] 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

解法可以说很多了本质大同小异

1. 枚举法

#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 2e6;

int arr[MAXN];
int brr[MAXN];

int main()
{
	int n, ans, flag = 1, len;
		cin>>n>>ans;
		
	for(int i = 0; i < n; i++)
	{
		cin>>arr[i];
		len = flag;
		for(int j = 0; j < len; j++)
		{
			if(arr[i] + brr[j] == ans)
			{
				cout<<"Yes"<<endl;
				return 0;
			}
			else if(arr[i] + brr[j] < ans)
			{
				brr[flag ++ ]= arr[i] + brr[j];
			}
		}
		/*for(int j = 0; j < flag; j++)
			cout<<brr[j]<<' ';
		cout<<endl;*/
	}
	cout<<"No"<<endl;
	return 0;
}

2.dfs

#include <iostream>
using namespace std;

int a[110];
int n, ans;
int flag = false;

void dfs(int nowsum, int pos)
{
	if(nowsum > ans)
		return ;
	if(nowsum == ans)
	{
		flag = true;
		return ;
	}
	for(int i = pos + 1; i <= n && !flag; i++)
	{
		dfs(nowsum + a[i], i);
	}
}
int main()
{
	cin>>n>>ans;
	
	for(int i = 1; i <= n; i++)
		cin>>a[i];
		
	dfs(0,0);
	
	if(flag)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
		
	return 0;
}

3。dp

typedef long long ll;
using namespace std;
ll a[1000005];
ll dp[1000005];
int main()
{
    ios::sync_with_stdio(false);
    ll n,m;
    while(cin>>n>>m)
    {
        ll flag=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=m;j>=a[i];j--)
            {
                dp[j]=max(dp[j-a[i]]+a[i],dp[j]);
                if(dp[j]==m)
                {
                    flag=1;
                    cout<<"Yes"<<endl;
                    break;
                }
            }
            if(flag==1)break;
        }
        if(flag==0)cout<<"No"<<endl;
    }
    return 0;
}