I have a warehouse in which I keep goods. Each article occupies given volume of warehouse space and costs give amount of dollars.
Now, because warehouse is full and I'm expecting new delivery, I have to free some space - no less than the new delivery will occupy, but I also have to minimize my loses. In other words, I have to empty at least X cubic meters of warehouse space by throwing out some articles, making sure that value of those articles is the minimum value possible.
Example: If X=10m3, then I prefer to throw out item that occupies 20m3 and is worth 1000$ than item that occupies exactly 10m3 but is worth 2000$. Of course in the real calculation it will be necessary to throw out more than one item, probably 5, 10 or maybe even 20.
What I'm thinking of is to represent the above problem as a tree, with nodes representing volume of emptied space and edges representing lost value, then searching for nodes that have value greater or equal to X and then choosing the node that has the lowest lost value along the edges from tree root to that node.
What I'm not sure if this is good approach because for e.g. 100 items in warehouse full tree would have 100 nodes on first depth level, 100*99=9900 nodes on second level etc, so this quickly starts to be prohitibive.
Is there better approach, or maybe even some proven algorithm (that I'm not aware of) for such kind of problems?