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.
For example:
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?