What you describe sounds like a variation on the Knapsack Problem (but I am guessing you already knew that). I have not kept up with the state-of-the-art in dealing with that problem (or any NP-complete problems, actually), but that would be where I would start for theory. In practice, if you are within a single-digit percentage of best results, I would leave it there unless your working set reaches a size where that difference becomes problematic.

Hope that helps.