Variation of subset sum

1
votes

Given an array of numbers I want to find out set of numbers whose sum is a multiple of Given number.

I know this is variation of subset sum. But the problem is that there are infinite multiples of a number. So I can't think of a Dynamic Problem Solution to the problem.

So how to extend subset sum problem to it?

3
algorithmdynamic-programmingsubsetsubset-sum
Useful link - Pham Trung
Why? Should be enough for you to start? dp state can be[index][modulus with given number]. - Pham Trung
@PhamTrung I meant the link was taking to invalid page first. Now the link is fixed thanks. - coder hacker
@PhamTrung But its strange people using Quora instead of SO - coder hacker
Knowledge comes from every source :) IMO even though SO has more reputation in term of programming, but Quora is growing fast. - Pham Trung

3 Answers

1
votes

Pseudo polynomial DP solution to subset sum uses the DP state:

DP(n, s) = Number of ways of getting a sum of s using first n elements of the set

And takes O(ns) time. If I want to find all the multiples of d, I am only interested in remainders of subset sums with d. Remember modulo is distributive. Therefore, I change the DP state to

DP(n, m) = Number of subsets whose sum = m mod d using the first n elements

Space reduced to O(nd) and time also O(nd) One convention followed in the actual pseudopolynomial solution is to traverse the DP array from the end, allowing you ro use only O(s) space. That cannot be done here. The best you can do is to use O(2m) memory to store previous and current DP arrays.

0
votes

Although there are infinitely many multiples of every (nonzero) number, there are only finitely many multiples of a number that will be less than the sum of all the elements in your set. In other words, you can always upper-bound the maximum multiple that could be generated by the sum of the elements of the set. This should enable you to use standard pseudopolynomial-time DP techniques to solve the problem.

Hope this helps!

0
votes

Here is code for finding the number of ways you can calculate the sum value.

public static void main(String[] args) {

    Scanner scan=new Scanner(System.in);
    int n=scan.nextInt();//number of elements in the set
    int m=scan.nextInt();//sum needs to be calculated
    scan.nextLine();

    int[] setValue=new int[m];
    long[][] setSplit=new long[m+1][n+1];
    for(int i=0;i<m; i++)
        {
        setValue[i]=scan.nextInt();
    }
    setSplit[0][0]=1;
    //when sum is 0
    for(int i=1; i<m+1; i++)
        {
        setSplit[i][0]=1;
    }
    //when sum is more than 0 but set element is 0
    for(int j=1; j<n+1; j++)
            {
            setSplit[0][j]=0;
        }
    int temp=0;
    for(int i=1; i<=m; i++)
        {

        for(int j=1; j<n+1; j++)
            {
            setSplit[i][j]=setSplit[i-1][j];
            if(j>=setValue[i-1])
                {     

                setSplit[i][j]=setSplit[i][j]+setSplit[i][j-setValue[i-1]];

            }
        }

    }
   // System.out.println(Arrays.deepToString(setSplit));

    System.out.println(setSplit[m][n]);/*this will give number of ways sum can be calculated*/ 
}