we have to find partition such that average of two partitions are same, it seems that we need to solve the problem of finding all possible sum for a subset of size k (for 1<=k<=n/2), where n is total # of items.

Let S1 = sum of partition 1

n1 = # of items in partition 1

S2 = sum of partition 2

n2 = # of items in partition 2

S = S1+S2

n = n1+n2

Since, S1/n1 = S2/n2, it implies S1/n1 = S2/n2 = (S1+S2)/(n1+n2) = S/n

Now, we populate a table of size (N/2) x N x S, where each entry T[k][i][j] is 1 if we there exists some subset of size k using the set of elements {1,2,...,i} that sum to j. During the computation of this table entries, if we ever found that j/k = S/n, there exists a way to make a partition with equal average. T[k][i][j] can be generated as a recurrence like :

`T[k][i][j] = T[k-1][n-1][j-item_i] || T[k][i-1][j]`

`An example to follow above idea:`

`items = {2, 4, 4, 6, 6, 8}`

N = 6, S = 30, Avg = 5

for k = 2, we can generate T[2][4][10] = 1

which implies Avg. of this partition = 10/2 = 5

TC would be O(N^2*S), space could be reduced to O(N*S).

public class Partition {

public static void main(String[] args) {

int [] A = {2, 4, 4, 6, 6, 8};

partitionEqualAvg(A);

}

public static void partitionEqualAvg(int [] A) {

int n = A.length;

int S = sumOfArray(A);

double avg = S/n;

int subsetLen = n/2;

boolean [][][] T = new boolean[subsetLen+1][n+1][S+1];

for (int i=0; i<=n; i++) {

T[0][i][0] = true;

}

for (int k=1; k<=subsetLen; k++) {

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

for (int j=1; j<=S; j++) {

if (A[i] <= j) {

T[k][i][j] = T[k-1][i-1][j-A[i]];

}

T[k][i][j] = T[k][i][j] || T[k][i-1][j];

if (T[k][i][j]) {

double tempAvg = (double)j/(double)k;

if (Math.abs((tempAvg - avg)) <= 0.0001 ) {

System.out.println("Partition 1: sum " + j + " of " + k +" items");

System.out.println("Partition 2: sum " + (S-j) + " of" + (n-k)+" items");

return ;

}

}

}

}

}

System.out.println("No partition with equal average possible!");

}

public static int sumOfArray(int [] A) {

int len = A.length;

int sum = 0;

for (int i=0; i<len; i++) {

sum += A[i];

}

return sum;

}

}

## 2 comments:

Which language I can test above sample

@ali, Code is in Java...

Post a Comment