CODEWITHSUNDEEP
arraysalgorithm
xjufo
xjufo

Reputation: 1

Find max common sum of subsets of 2 arrays

Given 2 Arrays of Intergers (unsorted, may contains duplicate elements), e.g.:

int[] left = {1, 5, 3};
int[] right = {2, 2};

We can get sums of subset of left array by picking or not picking up each element (2^n combinations), so, all the possbile sums could be (remove the duplicate sums):

{0, 1, 3, 4, 5, 6, 8, 9}

Same thing to the right array, sums of subset of right array are:

{0, 2, 4}

Then, the max common sum of subsets of these 2 arrays is 4, because 4 = left[0] + left[2] = rihgt[0] + right[1] and it's the max.

Question: how to get max common sum and indexes to construct this sum from 2 arrays? (if there are multipe combinations could get the same max sum in one array, just need to return one combination) Any better way to get the max common sum without caculating out all the possbile sums of subset?

Upvotes: 0

Views: 331

Answers (2)

Armali
Armali

Reputation: 19375

Based on the method pointed out by risingStark for finding the maximum common sum and on Print all subsets with given sum for finding indexes of summands, and since the question uses Java syntax, here's an unoptimized and unbeautified Java program with some example data sets:

import java.util.Arrays;
import java.math.BigInteger;

public class _68232965
{
    static int sum;
    static boolean found;
    public static void main(String[] args)
    {
        { int[][] lr = { {1, 5, 3},   {2, 2} }; maxcommsum(lr); }
        { int[][] lr = { {1,1,2,3,4}, {2, 2} }; maxcommsum(lr); }
        { int[][] lr = { {1, 2, 3},   {2, 2} }; maxcommsum(lr); }
        { int[][] lr = { {3,3,3,10},  {9,13} }; maxcommsum(lr); }
    }
    static void maxcommsum(int[][] lr)
    {
        for (var a: lr) System.out.println(Arrays.toString(a));
        var s = new BigInteger[] { BigInteger.ONE, BigInteger.ONE };
        for (int j, i = 0; i < 2; ++i)
            for (j = 0; j < lr[i].length; ++j) s[i] = s[i].shiftLeft(lr[i][j]).or(s[i]);
        while (s[0].bitLength() != s[1].bitLength())
        {   // find the maximum common sum
            int larger = s[0].bitLength() < s[1].bitLength() ? 1 : 0;
            s[larger] = s[larger].clearBit(s[larger].bitLength()-1);
        }
        sum = s[0].bitLength()-1;
        System.out.println("sum = "+sum);
        for (var a: lr) { found = false; f(a, 0, 0); System.out.println("<= indexes"); }
    }
    static void f(int[] pat, int i, int currSum)
    {   // find indexes of summands
        if (currSum == sum)
        {
            found = true;
            return;
        }
        if (currSum < sum && i < pat.length)
        {
            f(pat, i+1, currSum + pat[i]); if (found) { System.out.print(i+" "); return; }
            f(pat, i+1, currSum);
        }
    }
}

Upvotes: 0

risingStark
risingStark

Reputation: 1155

I think this solution using bitsets in C++ will work.

// returns maximum possible common subset sum
int fun(int left[], int right[]){
    // for the given constraints, the maximum possible sum is 10^7
    bitset<10000001> b, b1;
    int n = // size of left array
    int m = // size of right array
    b[0] = b1[0] = 1;
    for(int i=0;i<n;i++){
        b|=b<<left[i];
    }
    for(int i=0;i<m;i++){
        b1|=b1<<right[i];
    }

    // After the above loop, b and b1 contains all possible unique values of subset sum.
    // Just loop from the most significant bit and find the position in which the
    // bits of both, b and b1 are set.
    // That position is the maximum possible common subset sum
    // For indices, any standard algorithm for finding subset-sum
    // for a particular sum will do.
}

Upvotes: 1

Related Questions