Classifier that optimizes performance on only a subset of the data?
I want to clarify that the fact that you can pick only 100 boxes from the test dataset is NOT a limitation (like you describe it). You just need to see it from this perspective:


  How to pick the 100 boxes (out of 500K) that MOST LIKELY contain gold?


A very suitable algorithm would be a Decision Tree classifier. By using the Information Gain (based on Entropy Reduction), it can learn which features can split the dataset more accurately into two classes, i.e. the one that contains gold and the one that doesn't, and neglect (prune) the weakest attributes. After that, you will not only have a trained classifier but also gain insight on which features are the most important to make the decision (very important information).