小偷的背包(0963)

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。如果有满足条件的选择，则此背包有解，否则此背包问题无解。

Description

第一行为物品重量S（整数）；第二行为物品数量n，第三行为n件物品的重量的序列。

Input

有解就输出“yes!”，没有解就输出“no!”。

Output

20
5
1 3 5 7 9

Sample Input

yes!

#include<iostream>
using namespace std;
int a[100];
int fun(int w, int n)
{
    if (w == 0)return 1;
    if (w != 0 && n == 0)return 0;
    if (fun(w - a[n], n - 1))return 1;
    return fun(w, n - 1);
}
int main()
{
    int w, n;
    cin >> w >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    if (fun(w, n))
        cout << "yes!";
    else
        cout << "no!";
    return 0;
}

View Code