很经典的01背包模型

#include <bits/stdc++.h>
using namespace std;
int w[1000], dp[1000], s, n;
int main()
{
	while (cin >> s >> n)
	{
		memset(dp, 0, sizeof(dp));
		memset(w, 0, sizeof(w));
		for (int i = 1; i <= n; i++)
			cin >> w[i];
        //开始动规，一定要从后往前更新
		for (int i = 1; i <= n; i++)
			for (int j = s; j >= w[i]; j--)
				dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
		cout << (dp[s] == s ? "YES\n" : "NO\n");
	}
	return 0;
}