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)
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!