Algorithms - Dynamic programming - Subset sum of two arrays

Question

My homework include a dynamic programming question:

Given two arrays of natural integers (a1,a2,...,an and b1,b2,...,bn) such all of them are smaller than n^2, and also given is a number B which is smaller than n^3.

You need to determent if there is an array (c1,c2,...,cn) such:

And for each 1 <= i <= n, ci = ai or ci = bi.

*This algorithm must be written with dynamic programming.

*Also, what would we need to change to acctually get the array c that gives us Sum(c) = B

Another way of looking at the question is by saying that c is equal to a subset of a, and its complement subset from b.

This is a recursive pseudo code I wrote to solve this question:

W(a,b,i, N)
    if i==-1
        if N==0     return true;
        else        return false;
    return W(a,b,i-1,N-a[i]) || W(a,b,i-1,N-b[i]);

T(n) = 2^n

And here, to return the best path, just store this in a tree, and go over from the (good) end to the start

How can I write this with dynamic programming? Will this even help the run time? because the recursive solution has independent results.

*I searched google for this problem and found nothing but "the subset sum problem" which is different.

Hmm, I think you are very close to the dynamic programming solution. Just need to add a dp table into the recursive method, and you are done. About the time complexity, in this case, it will be equaled to the size of your dp table. — Pham Trung
I do not understand (logically) how can a table representation help here. We have 2^n calls, that I better represent as a tree. How will it work? — Amit
This is the normal subset-sum in a very thin disguise. Consider a new array d[i] = a[i] - b[i] and a new number g = n - sum(b). Solve subset-sum(d,g) and you have a solution for your original problem. — n. 1.8e9-where's-my-share m.
@Amit you need to read more about dynamic programming. Basically, dp works like a cached layer, whenever you meet a state that you calculated before, you immediately return the result, without making any further steps/methods calling. So, the number of method calls is bounded by the number of state. — Pham Trung
@Amit your understanding is not correct, for example, start from N = 10, and a = {1,2,3}, b = {2,3,2}. After two steps, you can travel from state (N = 10, 2) to state (N = 5, 0) by two ways a3 + a2 or b3 + b2. So, without dp, you will repeatedly call function (a, b, 0, 5) twice. — Pham Trung

Amit Amit · Accepted Answer · 2015-12-14T07:43:19

Thanks to @PhamTrung I have a solution:

Let there be a matrix [B,n] (max size [n^3,n])

Example: (n=3, B=8)

    0   1       2       3       4       ... 8
0   T   F       F       F       F       ... F
1   F   (1,1)   (1,2)   (1,3)   (1,4)   ... (1,8)
2   F   F       (2,2)   (2,3)   (2,4)   ... (2,8)
3   F   F       F       (3,3)   (3,4)   ... (3,8)

Pseudo Code:

//Generate the matrix
A = new Array(n+1,B+1)
for(i: 0 to n) //run over lines
    for(j: 0 to B) //run over B columns
        if i==0 //if we are in the first row
            A[i,j] = j==0; //if this is [0,0], it is true. else, false
        else if i>j //if we have more numbers than the sum
            A[i,j] = false; //it cannot happen
        else
            //general case:
            //if we remove a[i] or b[i], will we get to a true statement?
            A[i,j] = (j-a[i] >= 0 && A[i-1, j-a[i]]) || (j-b[i] >= 0 && A[i-1, j-b[i]]);

is_set(n,B,A)
    if(A[n,B])
        return true;
    return false;

Formulas:

[0,j],j!=0 = F
[0,0]   = T
i > j   = F
i <= j  = (i-1, j - a[i]) || (i-1, j - b[i])

Getting the route:

To get the route constructing C, we will also save in each true point 0(=a) or 1(=b), and just go over from the bottom to the top.

Algorithms - Dynamic programming - Subset sum of two arrays

1 Answers