Can anyone help me with a problem? It is from USACO. I solved all other problems from this chapter, but I stuck on this one. I'm solving it from last week but I can't find any optimal solution. Please help me if you can. Here I will explain problem statement shortly:

There are N knapsacks with their capacitance S[i], 1 <= i <= N & 1 <= N <= 50 (S[i] is integer, but range of it is not given). And M objects with their weight W[i], 1 <= i <= M & 1 <= M <= 1023 & 1 <= W[i] <= 128. You can use one object once and you have to take maximum number of objects in all knapsacks.

INPUT:

4

30 40 50 25

10

15 16 17 18 19 20 21 25 24 30

OUTPUT:

7

There is given hint: This is a high dimensionality multiple knapsack problem, so we just have to test the cases. Given that the search space has a high out-degree, we will use depth first search with iterative deepening in order to limit the depth of the tree. However, straight DFSID will be too slow, so some tree-pruning is necessary.

Please help and give me pseudocode if you can.