Find the closest sum possible to a given sum from rows of a matrix

Question

I should design an algorithm, using dynamic programming, that gets as an input a matrix, named A, with n rows and k columns. Each cell in matrix A contain a natural number. You also get a number that represents a limited sum, and you should choose only one number from each row, to get the closest sum possible to the limited sum that you were given (calculated sum should be <= limited sum)

For example:

A:
1 2 3
4 5 6
7 8 9

• Limited sum: 20
  The answer should be: 18
• Limited sum: 17
  The answer should be: 17

---‐------------

I thought about taking another matrix, called B, with n rows and the limited sum that I got as the columns number. At the first row of B, to put the value 1 only in the indexes that exists in row 1 in matrix A. At the second row of B, to take every element in the second row of matrix A and add it to every index value in the first row of B that contains 1 in it (if you exceed the limited sum, you're jumping to the next element in row 2 on matrix A). And so on until you get to the final row of B. At the end of the process, you take from the final row of B the largest index that contains the value 1, and this is the answer.

I thought about this solution, but I'm pretty much sure that it's not the most efficient that i can get.

If someone has another direction, clue or suggestion, I'll really appreciate it!

Answer 1

Your algorithm is pseudo-polynomial, since it is polynomial in the parameter $\operatorname{max\_sum}$ that is inputted using $\log(\operatorname{max\_sum})$ bits. However we will show that your problem is NP-complete, therefore your algorithm, although in practice exponential, is a reasonable choice.

Let's define the Subset Sum Problem (SSP):

given $a_1, \dots a_n \in \mathbb{Z}$ decide whether exists $S\subseteq \{1,\dots n\}$ such that $\sum_{i \in S} a_i = 0$.

SSP is NP-complete, thus it is sufficient to reduce an instance of SSP to your problem to get the hardness result.

As an intermediate step let's reduce SSP to a particular case of SSP, having only one negative value. To do so split $\{1, \dots n\}$ into $P = \{i \in \{1, \dots n\} \, | \, a_i \geq 0 \}$ and $N = \{1, \dots n\} \setminus P$ and define another instance of SSP of size $n+1$ as follows:

\begin{equation*} b_i = \begin{cases} a_i & \text{if }\, i \in P\\ -a_i & \text{if } \, i \in N \\ \sum_{j \in N}a_j & \text{if } \, i = n + 1 \end{cases} \end{equation*} Here $b_{n+1}$ is the only negative value. Now define a bijection (computable in polynomial time) between feasible solutions of the two problems:

$$ S \subseteq \{1, \dots n\} \mapsto S^\prime = (P \cap S) \cup (N \cap S^c) \cup \{n + 1\}$$

Then it holds

$$ \sum_{i \in S} a_i = \sum_{i \in S^\prime} b_i$$

and solving the new instance we solve the original one as well in polynomial time.

To conclude it suffices to notice that the solution of the new instance of SSP is entailed by the solution of your problem for $k = 1$ setting $\operatorname{max\_sum} = b_{n+1}$, in fact it admits a soliuton if and only if the closest sum is exactly $\operatorname{max\_sum}$ .