算法 - 动态规划 - 两个数组的子集和

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

看待这个问题的另一种方式是说 c 等于 a 的子集及其来自 b 的补子集。

这是我为解决这个问题而写的递归伪代码:

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

在这里，要返回最佳路径，只需将其存储在树中，然后从(好的)末端到起点

我如何用动态规划来写这个？这甚至有助于运行时间吗？因为递归解有独立的结果。

*我在谷歌上搜索了这个问题，除了“子集和问题”之外什么也没找到。

Answer 1

感谢@PhamTrung 我有一个解决方案:

设矩阵[B,n](最大尺寸[n^3,n])

示例:(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)

伪代码:

//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;

公式:

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

获取路线:

为了得到构造C的路径，我们也会在每个真实点中保存0(=a)或1(=b)，从下往上走一遍即可。