简单背包问题

简单背包问题

1000(ms)

65535(kb)

1438 / 6830

Tags: 搜索

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。 

问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。 

如果有满足条件的选择，则此背包有解，否则此背包问题无解。

 

输入

输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）

多组测试数据。

输出

对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“

样例输入

20 5
1 3 5 7 9

样例输出

YES

//#include <iostream>
//#include<malloc.h>
//using namespace std;
//
//main()
//{
//   char *c1 = "abc";
//
//   printf("%d %d %c %d %s\n",&c1,c1,*c1,*c1,c1);
//
//   getchar();
//}   
#include<iostream> 
#include<stdio.h> 
#include<malloc.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;

int a[100],visit[100],k=0,wi,n;;
void def(int sum){
	if(sum==wi)
		k=1;
	else{
		for(int i=0;i<n;i++){
			if(visit[i]==0){
				visit[i]=1;
				def(sum+a[i]);
				visit[i]=0;
			}
		}
	}
}
 
int main() {

	while(cin>>wi>>n){
	for(int i=0;i<n;i++)
		cin>>a[i];
	k=0;
	def(0);
	if(k==1)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	}
 	return 0;
}