I have some sets (A, B, ...) each containing some vectors (e.g. [1, 0, -1]). How can I pick exactly one vector per set such that they sum to a specified target vector?For example:A: { [1, 0, -1], [3, 0, 0], ... }B: { [0, -1, -1], [2, -1, 0], ... }Target: [3, -1, -1]Solutions:1) A=[1, 0, -1], B=[2, -1, 0]2) A=[3, 0, 0], B=[0, -1, -1]I think this is a variation of the multi-dimensional knapsack problem with the added 'one-per set' constraint. Has this been written about anywhere?For my domain, there are 30 sets each containing 50 vectors with 30 dimensions. These vectors are sparse with ~80% zeroes. There is at most one negative number per vector.Any pointers to research papers or proposed algorithms would be hugely appreciated.Thanks.
Multi-dimensional Knapsack with added one-per-group constraint
algorithms;complexity theory;knapsack problems