Dynamic programming problems

Question

I'm looking for some pointers about a dynamic programming problem. I cannot find any relevant information about how to solve this kind of problem. The only kind of problem I know how to solve using dynamic programming is when I have two sequences and create a matrix of those sequences. But I don't see how I can apply that to the following problem...

If I have a set A = {7,11,33,71,111} and a number B. Then C which is a subset of A, contains the elements from A which builds the sum B.

EXAMPLE:

A = {7,11,33,71,111}
If B = 18, then C = {7,11} (because 7+11 = 18)

If B = 3, then there is no solution

Thankful for any help here, I just don't know how to think when solving these kind of problems. I cannot find any general method either, only some examples on gene sequences and stuff like that.

Answer 1

Dynamic programming is a broad category of solutions wherein a partial solution is kept in some structure for the next iteration to build upon instead of having it recalculate the intermediate results over and over again.

If I were to take a dynamic approach to this particular problem, I would probably keep a running list of every sum calculable from the previous step, as well as the set used to compute that sum.

So for example the first iteration my working set would contain {null, 7}, then I would add 11 to everything in that that set as well as the set itself (let's pretend that null+11=11 for now). Now my working set would contain {null, 7, 11, 18}. For each value in the set, I would keep track of how I got that result: so 7 maps to the original set {7} and 18 maps to the original set {7,11}. Iteration would end when either A) the target value is generated or B) the original set is exhausted without finding the value. You could optimize the negative case with an ordered set, but I'll leave figuring that out to you.

There is more than one way to approach this problem. This is a dynamic solution, and it's not very efficient as it needs to build a set of 2^(size of set) members. But the general approach corresponds to what dynamic programming was created to solve.

Answer 2

I think this will definitely answer your question.