# Placing items into compatible bucket types to find an optimal total value

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?

You can formalize this problem as a minimum-cost flow problem.

You construct the graph as follows.

• First construct a source vertex $$s$$ and a sink vertex $$t$$.

• For each item $$i$$, add a vertex $$u_i$$ and add an edge from $$s$$ to $$u_i$$ with capacity 1 and with cost equal to the negation of the value of item $$i$$.

• For each bucket $$j$$, add a vertex $$v_j$$ and add an edge from $$v_j$$ to $$t$$ with capacity equal to the capacity of bucket $$j$$ and with cost 0.

• If item $$i$$ is compatible with bucket $$j$$, add an edge from $$u_i$$ to $$v_j$$ with capacity 1 and with cost 0.

Now you can use some polynomial time algorithm (for example, the cycle canceling algorithm) to find an integral solution of the minimum-cost flow problem. This integral solution then shows how you assign the items: if there is a flow 1 on $$(u_i, v_j)$$, then assign item $$i$$ to bucket $$j$$.

• I was indeed able to solve this by using this method. There is a similar example of this being done in javascript here. The difference is that in this wedding example they are using a constant cost of zero for each edge, which in my case is replaced by the negation of the value of the item as per @xskxzr 's answer. Feb 26, 2019 at 22:49