Jamik's blog

By Jamik, 9 years ago, translation, In English

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.



30 40 50 25


15 16 17 18 19 20 21 25 24 30



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.

Read more »

  • Vote: I like it
  • +1
  • Vote: I do not like it