# Dynamic programming: multiple subset sum

The subset sum problem is finding a solution $x \in \{0,1\}^n$ such that $$\sum_{i=1}^n a_i x_i = c,$$ for $a_i, c \in \mathbb{F_q}$ (also possible for $a_i,c \in \mathbb Z$).

I know that there exists a pseudo polynomial solution to this via dynamic programming. Sadly I am not very skilled at dynamic programming yet so I was wondering if a pseudo polynomial solution was possible to the following variation on a multiple subset sum problem.

Instead of $1$ equation we are working with $2$ or more, so we need to find a solution $x \in \{0,1\}^n$ such that $$\sum_{i=1}^n a_i x_i = c_1,$$ $$\sum_{i=1}^n b_i x_i = c_2,$$ for $a_i,b_i, c_1, c_2 \in \mathbb{F_q}$.

To give you some intuition, when we would have $n$ such equations this would be solvable via Gaussian elimination.

In this case all the coefficients are positive and bounded.

I was wondering if this would be solvable via dynamic programming such that we would have a pseudo polynomial algorithm or if this isn't possible an explanation why.

I hope you guys can help me!

• What is $\mathbb F_q$? – 5xum Sep 20 '15 at 14:26

Afterwards, you may run it for the first equation (check if there is a subset of $a_1, \ldots, a_n$ that sums up to $c_1$), and then check if any of the found solutions work for $b_1, \ldots, b_n$ and $c_2$.