algorithm - 子集和 N 阵列解决方案，需要动态解决方案

Question

尽管您可以拥有任意数量的array，但让我们假设您有两个array {1,2,3,4,5,6} 和{1 ,2,3,4,5,6} 您必须确定它们在两个 array 元素的参与下总和是否为 4。即

1 from array1, 3 from array2
2 from array1, 2 from array2
3 from array1, 1 from array2

等等

简而言之:想要实现子集求和算法，其中有两个数组，并且从两个数组中选择数组元素来组成目标求和

这是我用于一个数组的子集求和算法

bool subset_sum(int a[],int n, int sum)
{
 bool dp[n+1][sum+1];


   int i,j;

   for(i=0;i<=n;i++)   
      dp[i][0]=true;

   for(j=1;j<=sum;j++)
        dp[0][j]=false;

   for(i=1;i<=n;i++)

    {

        for(j=1;j<=sum;j++)

       {

           if(dp[i-1][j]==true)

              dp[i][j]=true;

           else
           {

               if(a[i-1]>j)

                   dp[i][j]=false;

                else

                    dp[i][j]=dp[i-1][j-a[i-1]];

            }

        }

    }
  return dp[n][sum];
}

Answer 1

我们可以用 3 维 dp 来实现它。但为了简单性和可读性，我使用两种方法编写了它。

注意:当我们从每个数组中选择至少一个元素时，我的解决方案有效。如果存在我们必须从每个 array 中选择相同数量的元素的条件，它就不起作用。

// This is a helper method

//  prevPosAr[] is the denotes what values could be made with participation from ALL
// arrays BEFORE the current array

// This method returns an array which denotes what values could be made with the
// with participation from ALL arrays UP TO current array


boolean[] getPossibleAr( boolean prevPossibleAr[], int ar[] )
{
    boolean dp[][] = new boolean[ ar.length + 1 ][ prevPossibleAr.length  ];
    // dp[i][j] denotes   if we can make value j using AT LEAST
    // ONE element from current ar[0...i-1]

    for (int i = 1; i <= ar.length; i++)
    {
        for (int j = 0; j < dp[i].length; j++)
        {
            if ( dp[i-1][j] == true )
            {
                // we can make value j using AT LEAST one element from ar[0...i-2]
                // it implies that we can also make value j using AT LEAST
                // one element from ar[0...i-1]
                dp[i][j] = true;
                continue;
            }

            int prev = i-ar[i-1];
            // now we look behind


            if ( prev < 0 )
            {
                // it implies that ar[i-1] > i
                continue;
            }

            if ( prevPossibleAr[prev] || dp[i-1][prev] )
            {
                // It is the main catch
                // Be careful


                // if ( prevPossibleAr[prev] == true )
                // it means that we could make the value prev
                // using the previous arrays (without using any element
                // of the current array)
                // so now we can add ar[i-1] with prev and eventually make i



                // if ( dp[i-1][prev] == true )
                // it means that we could make prev using one or more
                // elements from the current array....
                // now we can add ar[i-1] with this and eventually make i

                dp[i][j] = true;
            }
        }
    }

    // What is dp[ar.length] ?
    // It is an array of booleans
    // It denotes whether we can make value j using ALL the arrays 
    // (using means taking AT LEAST ONE ELEMENT)
    // before the current array and using at least ONE element 
    // from the current array ar[0...ar.lengh-1] (That is the full current array)

    return dp[ar.length];
}



// This is the method which will give us the output
boolean subsetSum(int  ar[][], int sum )
{
    boolean prevPossible[] = new boolean[sum+1];
    prevPossible[0] = true;


    for ( int i = 0; i < ar.length; i++ )
    {
        boolean newPossible[] = getPossibleAr(prevPossible, ar[i]); 
        // calling that helper function
        // newPossible denotes what values can be made with
        // participation from ALL arrays UP TO i th array
        // (0 based index here)



        prevPossible = newPossible;
    }

    return prevPossible[sum];
}