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.
Why did you choose Russian as the language of this post?
I forgot to change it. I use CF in Russian language, but problem statement is in English, because of this) I changed it, thanks!