TopCoder problem "KnapsackProblem" used in TCHS07 Semifinal (Division I Level Three)



Problem Statement

    We have several items and a bag that can carry a maximum weight of C. The i-th element of x is the weight of the i-th item. Return the number of different sets of items you can carry in the bag. Two sets are considered different if there exists at least one item which is included in one set and not included in the other.
 

Definition

    
Class:KnapsackProblem
Method:numberOfWays
Parameters:int[], int
Returns:int
Method signature:int numberOfWays(int[] x, int C)
(be sure your method is public)
    
 

Constraints

-x will contain between 1 and 30 elements, inclusive.
-Each element of x will between 1 and 10^9, inclusive.
-C will between 0 and 10^9, inclusive.
 

Examples

0)
    
{1}
1
Returns: 2
We can either take the item or not take it.
1)
    
{1}
2
Returns: 2
Same as the first example
2)
    
{2, 2}
1
Returns: 1
We cannot take any of the items.
3)
    
{1,1}
2
Returns: 4
We can take both items, just the first item, just the second item, or no items.
4)
    
{1,1}
1
Returns: 3
This is the same as the previous example, but with a lower capacity bag. We cannot take both items in this case.
5)
    
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
30
Returns: 1073741824
We can take any subset of the items.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6742

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10763&pm=6742

Writer:

VitalyGoldstein

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Brute Force