The original version of subset sum problem is that, given a set of integers and an integer s, does any non-empty subset sum to s ?
I have a variant of this problem but on two different sets. Given two set of integers $a$ and $b$. Both of them have N elements. Also given two numbers $s_a$ and $s_b$. Find a binary vector $x \in \{0,1\}^N$ such that $a^Tx=s_a$ (I) and $b^Tx=s_b$ (II)
To solve this problem, my approach is to relate it to any existing NP problems such as subset sum, Knapsack, IP problem, etc. but so far I have not found any connections. Subset sum, both single and multiple version, can satisfy either (I) or (II), but not both. Knapsack is similar. Although I can play a trick by adding two constraints to force $b^Tx<s_b$ and $b^Tx>s_b$, that solution is not quite natural...
Is there any problems which is close to this problem ? 'close' here means that I can reduce one to the other or vice versa.
Thanks.
Obviously, this problem is NP complete as well.
If you could solve this problem, you could also solve the problem with all $b_i = 0$ and $s_b = 0$, solving Knapsack. (This is the only direction you have to prove.)
And on the other hand, obviously you can check any solution polynomial time.