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