Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a bucket type iff the item is able to be inserted into a bucket of that type. The goal is to insert the items into the buckets such that the total value of the inserted items is highest.
Items: compatible with | value A,B,C | 17.641 A,B,C | 14.821 A,B | 14.274 A,B | 13.755 A,B | 12.240 A,B | 12.240 B,C | 11.960 A,B | 10.270 A,B,C | 9.958 A,B,C | 8.552 Buckets: bucket type | capacity A | 2 B | 3 C | 4 Solution: bucket | values A | 17.641, 12.240 B | 14.274, 13.755, 12.240 C | 11.960, 9.958, 8.552, 14.821
Is this problem a special case of any existing problems? I am finding it hard to envision an algorithm to solve it, but I feel that a good solution would require passing over the item list multiple times and maintaining a queue of best matches for each bucket type.
What would be the wost-case complexity of the resulting algorithm? Could a situation with 5 bucket types and 30 items explode in computational expense?