Optimal way to pack items with multidimensional weight such that the number of items is minimized?

Question

I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, 0}, then item x does not have property 1, does have property 2, and does not have property 3.

I am also given a M dimensional "goal" vector indicating the number of items I need that match each property. For example, if my goal vector is: {1, 3, 2}, then I need 1 item with property 1, 3 items with property 2, and 2 items with property 3.

My question is, how can I select a subset of items from the set S such that the constraints listed in the goal vector are met exactly and so that the number of items selected from S is minimized? What is the name of this problem, and what is an efficient algorithm for solving it? Also, what algorithm would I use for the opposite scenario where I would like to maximize (instead of minimize) the number of items used?

Could this be a variation on the knapsack problem or the bin packing problem?

Answer 1

This problem is NP-hard, so you can't expect a general algorithm that is efficient and always correct. In particular, in the special case where the goal vector has only 1's and 0's in it, it becomes an instance of the exact cover problem.

Your problem can be viewed as an instance of the multidimensional subset sum problem.

If you have to solve it in practice, I would suggest formulating it as an instance of integer linear programming and using an off-the-shelf ILP solver.