小偷的背包问题，数据结构


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

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

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

样例输入
20
5
1 3 5 7 9

样例输出
yes!

#include<iostream>
using namespace std;
int x[101];
int test(int w, int k)
{
    if (!w) return 1;
    if (w<0 || w>0 && !k) return 0;
    if (test(w - x[k], k - 1)) return 1;
    return test(w, k - 1);
}
int main()
{
    int  w, n, i;
    cin >> w >> n;
    for (i = 1; i <= n; i++)
        cin >> x[i];
    cout << (test(w, n) ? "yes!" : "no!");
    return 0;
}

这是就简单的01背包问题，用递归枚举时间复杂度2^n，去找找动态规划的，时间复杂度n*s

img

img