描述
小明最近做出了一道题：如何在一组数中寻找三个数,这三个数的和等于一给出的定值m，洋洋得意。于是小华不乐意了，小华说，你能找找在一组数字中是否有n个数,使得这n个数的和等于一给定的定值m吗？
1.0 < 数字大小 <= 1000
2. 0 < 序列中数字个数 <= 1000
3. 0 <= m <=1000
输入 多组数据，每组两行，第一行为序列内容，第二行为m的值。 输出 如能找到，输出Yes，否则，输出No。 样例输入 1 3 4 5 5 1 3 4 5 9 2 样例输出 Yes No 分析：给定一些数字，给定一个数字n，问你给定的一堆数字中是否能找出一些数字之和等于数字n
n为给定的界限，在这个界限里面放数字，看看能不能和为n
----------------------------------01背包
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> #include <stack> #include <string> using namespace std; string s; int a[1005]; int dp[1005]; int main() { while(getline(cin,s)) { int m; cin >> m; getchar(); int sum; int g = 0; for(int i = 0;i < s.length();i++) { sum = 0; while(s[i] >= '0'&&s[i] <= '9') { sum = sum*10+s[i]-'0'; i++; } a[g++] = sum; } memset(dp,0,sizeof(dp)); for(int i = 0;i < g;i++) { for(int j = m;j >= a[i];j--) dp[j] = max(dp[j],dp[j-a[i]]+a[i]); } if(dp[m] == m) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
