# What is the right algorithm to solve this problem?

The problem is - We have a series of boxes (A, B, C, D, ...). Each box contains bricks of different colours. For eg.

``````Box A - red, blue
Box B - blue, red, green

... and so on...
``````

and there are multiple versions of each of the boxes -

``````Box A1 - red, blue
Box A2 - green, red, yellow
...

Box B1 - blue, red, green
Box B2 - blue, red

... and so on ...
``````

The idea is to choose one of the versions of each of the boxes, such the total number of unique bricks is minimum. For eg. in this example -

``````Box A1 + Box B1 = blue, red, green (3 unique bricks)
``````

but

``````Box A2 + Box B1 = blue, red, green, yellow (4 unique bricks)
``````

So `Box A1 + Box B1` is the better choice.

We need to build a collection of such boxes, choosing at least one version of each box such that the total unique number of bricks is minimum.

Is there a known algorithm to solve this problem?

• This seems to be one of the many variants of the set covering problem, which is NP-hard. This would mean that there is not better correct algorithm than the obvious "try everything and compare". There may be incorrect, e.g. approximate algorithms which improve on this bound. Mar 25, 2019 at 17:26