SWUST OJ's 0032 Simple Backpack Problems

Let the weight of an item that can fit in a backpack be S. There are n items with weights w1, w2, w3, ...wn.

Ask whether it is possible to choose a number of these n items to put into a backpack such that the sum of the weights put in is exactly S.

If there is a choice that satisfies the condition, then this knapsack has a solution, otherwise this knapsack problem has no solution.

importation

There are multiple lines of input data, including the weight of the item put in as s, the number of pieces of the item n, and the weight of each item (the input data are all positive integers)



Multiple sets of test data.

exports

For each test instance, if the condition is met then output "YES", if it is not satisfied then output "NO“

Sample Input

20 5



1 3 5 7 9

Sample Output

YES

Analysis:

This type of question is a simple NP problem. For a backpack carrying weight S , we have N items, and let the weight of each item be stored in a corresponding position in the array arr[n].
Now we consider the general case where for each item i we have only two choices: to be <--or--> not to be
To i : then the remaining weight of the backpack S = S - arr[i] and the number of remaining items N = N - 1;
Don't i : Then the remaining weight of the backpack remains unchanged S = S, and the number of remaining items N = N - 1;

Now let's consider the exit condition (special case):
When S = 0, we have the solution and return true;
When N = 0, the items have been eliminated, so there is no solution and false is returned;
When arr[i] > S, this item weighs more (terminating the invalid recursion that follows) and is not solved, returning false;
This constructs a recursive function to solve the problem.

Code:

// : Defines the entry point to the console application.



//



 



#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);		    // Abandon the ith item, s is unchanged, and recursively call left to see if it has a solution




	bool R = NPSolve(s - arr[i], i + 1, n - 1);	//pick the i-th item, s changes, recursive right call to see if it has a solution




 



	return (L || R);



}



 



int main()



{



	int s, n;



	while (cin >> s >> n)



	{



		memset(arr, 0, sizeof(arr));            // Zero Setting




		for (int i = 0; i < n; i++)



			cin >> arr[i];



 



		if (NPSolve(s, 0, n))



			cout << "YES" << endl;



		else




			cout << "NO" << endl;



	}



    return 0;



}