设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。
问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。
如果有满足条件的选择，则此背包有解，否则此背包问题无解。
输入
-
输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）
-
多组测试数据。
输出
对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“样例输入
-
20 5
-
1 3 5 7 9
样例输出
YES分析：
这种类型的题属于简单NP问题。对于背包承重 S ，我们有 N 个物品，设每个物品重量保存在数组 arr[n] 中对应位置上。
现在我们考虑一般情况，对每个物品 i 我们只有两种选择：要<--or-->不要
要 i ：那么背包剩下承重 S = S - arr[i]，剩余物品个数 N = N - 1；
不要 i ：那么背包剩下承重不变 S = S，剩余物品个数 N = N - 1；
现在我们考虑一下退出条件（特殊情况）：
当 S = 0 时，我们已经得到解了，返回 true ；
当 N = 0 时，物品已经排除完了，所以没有解，返回 false ；
当 arr[i] > S 时，这个物品重量多了（终止后面无效的递归），也没解，返回 false ；
这样就构建一个递归函数解题。
代码：
-
// : 定义控制台应用程序的入口点。
-
//
-
-
#include<iostream>
-
#include<>
-
-
using namespace std;
-
int arr[100];
-
-
bool NPSolve(int s, int i, int n)
-
{
-
if (s == 0)
-
return true;
-
else if (n == 0 || arr[i] > s)
-
return false;
-
bool L = NPSolve(s, i + 1, n - 1); //放弃第i个物品，s不变，递归左调用看其是否有解
-
bool R = NPSolve(s - arr[i], i + 1, n - 1); //选取第i个物品，s改变，递归右调用看其是否有解
-
-
return (L || R);
-
}
-
-
int main()
-
{
-
int s, n;
-
while (cin >> s >> n)
-
{
-
memset(arr, 0, sizeof(arr)); //置零
-
for (int i = 0; i < n; i++)
-
cin >> arr[i];
-
-
if (NPSolve(s, 0, n))
-
cout << "YES" << endl;
-
else
-
cout << "NO" << endl;
-
}
-
return 0;
-
}
-
