TopCoder problem "CollectingMarbles" used in SRM 397 (Division II Level Three)



Problem Statement

    Maybe you don't know, but you are a fanatic of colored marbles. You want to collect them all, but you may not be able to carry them. You have numberOfBags bags, each of capacity bagCapacity grams. The i-th marble has a weight of marblesWeight[i] grams. You can go to the shop only once and you have enough money to buy all of the marbles. Return the largest number of marbles that you can carry home in the given bags.
 

Definition

    
Class:CollectingMarbles
Method:mostMarbles
Parameters:int[], int, int
Returns:int
Method signature:int mostMarbles(int[] marblesWeights, int bagCapacity, int numberOfBags)
(be sure your method is public)
    
 

Constraints

-marblesWeights will contain between 1 and 13 elements, inclusive.
-Each element of marblesWeights will be between 1 and 20, inclusive.
-bagCapacity will be between 1 and 20, inclusive.
-numberOfBags will be between 1 and 10, inclusive.
 

Examples

0)
    
{ 2, 2, 2, 2, 2 }
5
2
Returns: 4
We have 5 marbles, all weighting 2 grams and 2 bags with capacity of 5 grams each. We can put no more then 2 marbles into each bag.
1)
    
{ 1, 3, 5, 2, 4 }
5
2
Returns: 4
We can carry home marbles with weights 1, 2, 3 and 4.
2)
    
{ 7, 6, 6, 5 }
12
2
Returns: 4
We have enough space for all marbles.
3)
    
{ 2, 2, 2 }
1
10
Returns: 0
Here, we can't take anything.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12169&pm=8746

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Dynamic Programming