# 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. – Kilian Foth Mar 25 at 17:26