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:
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
My Approach:
Finding the maximum possible length of the 2 parallel pillars ie. floor(N/2). Then, using DP to find all the sum lengths that are possible using all the bricks. Starting with the highest possible sum possible <= floor(N/2), I take a single subset of elements that forms the sum. Then, again repeating the DP approach to find if the same sum can be formed using the remaining elements. If it can be formed, then the output is the highest possible sum, else using the 1st DP, check the next highest possible sum that can be formed and then, again iterate the whole process.
The problem with the above approach is that it checks for only one subset of elements to form the required sum. All possible subsets that can form the required sum should be checked and then for each of these subsets, using the remaining elements it should be checked if the same required sum can be formed. The trouble is the implementation of this in my current approach.
2nd Example-
N = 6
3, 2, 6, 4, 7, 1
Possible Sets:
(3, 2, 6) and (7, 4)
Answer: 11
The problem in my code might come in this case depending on the order in which elements (brick lengths) are given as input. It might be possible that the first set is formed using the elements (3, 7, 1) = 11 but the second set (2, 6, 4) cannot form sum = 11. Hence, my code starts to find the next possible maximum sum .ie. 10 which is wrong.
Can someone suggest better approaches or possible improvements in my current approach.
I think you can solve this with dynamic programming where for each pair (x, y) you work out whether it is possible to build pillars of length x and y using different bricks from the bricks considered so far.
Consider each brick in turn. At the start only (0, 0) is possible. When you see a brick of length L then for every possible pillar (x, y) there are three descendants - (x, y) (ignore the brick), (x + L, y) (use the brick on the first pillar), and (x, y + L) (use the brick on the second pillar).
So after you have considered all the bricks you will have a long list of possible pairs and you simply choose the pair which has two pillars of the same length and as long as possible. This will be practical as long as there are never too many different pairs (you can remove any duplicates from the list).
Assuming that the brick lengths are integers and the maximum pillar length is 1000 there are only 1001 * 1001 possible pairs, so this should be practical, and in fact it is probably easiest if you store pairs by having an array of size [1001, 1001] and setting entries [x, y] to 1 if pair (x, y) is possible and 0 otherwise.
For the first few steps of the example the reachable states are
(0,0) considering nothing
(0,3) (3,0) (0,0) considering 3
(0,5) (2,3) (0,3) (5,0) (3,0) (0,2) (2,0) (0,0) considering 3 and 2
The number of reachable states grows very fast at first but since we are only considering values from 0..1000 and we only care about whether an array is reachable or not we can maintain them using a boolean array of dimension 1001x1001