dfs 简单背包问题

#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<queue> using namespace std; int weight , n; int goods[50]; bool judge; void dfs(int step,int x) { if (x == weight) { judge = true; } if (step >= n) { return; } dfs(step + 1, x); dfs(step + 1, x + goods[step]); } int main() { while(~scanf("%d %d",&weight,&n)) { judge = false; for(int i=0;i<n;i++) { scanf("%d", &goods[i]); } dfs(0, 0); if(judge==true) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }