Constraint Sum Algorithm

Question

The problem I am trying to solve has a table of items:

Item | x | y | z | ... | n
================
A    | 2 | 3 | 1
B    | 6 | 6 | 8
C    | 9 | 2 | 1
D    | 1 | 5 | 7
.
.
.
w

The values of {x, y, z, ..., n} can be arbitrary and there can be an arbitrary number of rows and columns.

You would have constraints such that when you combine items together the sum is:

1. 7 <= sum(x) <= 10
2. 10 <= sum(y) <= 15
3. 8 <= sum(z) <= 10}

and

4. The number of items is 2 <= numItems <= 10

One possible solution is: A + B (x = 8, y = 9, z = 9)

The goal is to find all possible combinations that satisfy this. Or if that would take too long just some very small subset possible just one.

My question is is there any decent algorithm to solve this? This isn't a homework question or anything, it's for a personal project of mine. I've been trying to think of a good way of solving this but always seem to end up with very inefficient solutions. Hopefully I'm missing something.

Answer 1

This problem is NP-complete. You can easily reduce Subset-Sum to this problem as follows.

For a given input S,k of the subset-sum problem:

• Define a single column X containing all values in S
• Require k<=sum(X)<=k
• Require 1<=numItems<=|S|