2018-06-19

Create 2 pillars of equal maximum height from an array of bricks

Create two sub array of maximum equal height from an array.
Problem Statement:

There are N bricks (a1, a2, ...., aN). Each brick has length L1, L2, ...., LN). Make 2 highest parallel pillars (same length pillars) using the bricks provided.

Constraints:

There are N bricks. 5<=N<=50
Length of each brick. 1<=L<=1000
Sum of the bricks lengths <= 1000
Length of the bricks is not given in size order. There may be multiple bricks which may have the same length. Not all bricks have to be used to create the pillars.

Example:

1st Example-
N = 5
2, 3, 4, 1, 6
Possible Sets:
(2, 6) and (3, 4, 1)
Answer: 8

2nd Example-
N = 6
1, 5, 1, 6, 1, 1
Possible Sets:
(6, 1) and (1, 5, 1)
Answer: 7



Solution:



import java.util.*;

public class KNumberSubset {
private int number;
private int sum;
private LinkedList<Integer> subset;
private int[] numbers;
static LinkedList<LinkedList<Integer>> all=new LinkedList<>();

public KNumberSubset(int[] numbers, int number) {
this.numbers = numbers;
this.number = number;
sum = 0;
subset = new LinkedList<Integer>();
}

public void findSubset(int startPoint, int limit) {
if (sum == number) {
//System.out.println(subset + " :: " + sum);
all.add((LinkedList<Integer>)subset.clone());
//all.add(subset);

} else {
for (int i = startPoint; i < numbers.length; i++) {
sum = sum + numbers[i];
if (sum > limit) {
sum = sum - numbers[i];
break;
}
//subset.add((int) numbers[i]);
subset.add(i);
findSubset(i + 1, limit);
sum = sum - numbers[i];
subset.removeLast();
}
}
}

public static void main(String args[]) {
int[] numbers = {50,1,1,1,1};
int sum=0;
        for(int i=0;i<numbers.length;i++){
        sum=sum+numbers[i];
        }
        System.out.println("sum="+sum);
int number = sum/2;
Arrays.sort(numbers);
while(number>=0){
KNumberSubset ki = new KNumberSubset(numbers, number);
ki.findSubset(0, number);
LinkedList<LinkedList<Integer>> result=new LinkedList<>();
for(int i=0;i<all.size();i++){
for(int j=i+1;j<all.size();j++){
List<Integer> a1=(LinkedList<Integer>)all.get(i).clone();
List<Integer> a2=(LinkedList<Integer>)all.get(j).clone();
a1.retainAll(a2);
if(a1.isEmpty()){
result.add((LinkedList<Integer>)all.get(i).clone());
result.add((LinkedList<Integer>)a2);
}
}
}
if(!result.isEmpty()){
System.out.println("number = "+number);
break;
}
result.clear();
all.clear();
number--;
}
}
}

No comments:

Post a Comment