Meet In The Middle
描述
Meet in the Middle is an algorithmic technique that allows you combine results from two recursive calls efficiently.
Examples where it works:
Find 2 numbers from an array such that their sum is S. Complexity from O(N2) -> O(N)
Knapsack Problem
It works by in the following manner:
Break the given problem into two parts of equal length.
Find solutions to the two parts using brute force.
Now combine the results by picking an element in the first solution set, and searching for a corresponding element in the second solution set.
Notice that the above operation can only be done when merging the two solutions is an aggregate function. (Sum, Count, Max, Min…)
Return the result.
The time complexity of a problem goes from O(Nb) to O(N(b/2)). We see that the time complexity is still exponential, but the exponent is halved.
So, if we have N = 2 and b = 50,
Standard algorithm time: 250 = 12 days!
Meet in the Middle : 225 = 1 Second!
2.
Meet in the middle is a search technique which is used when the input is small but not as small that brute force can be used. Like divide and conquer it splits the problem into two, solves them individually and then merge them. But we can’t apply meet in the middle like divide and conquer because we don’t have the same structure as the original problem.
Split the set of integers into 2 subsets say A and B. A having first n/2 integers and B having rest.
Find all possible subset sums of integers in set A and store in an array X. Similarly calculate all possible subset sums of integers in set B and store in array Y. Hence, Size of each of the array X and Y will be at most 2n/2.
Now merge these 2 subproblems. Find combinations from array X and Y such that their sum is less than or equal to S.
One way to do that is simply iterate over all elements of array Y for each element of array X to check the existence of such a combination. This will take O( (2n/2)2) which is equivalent to O(2n).
To make it less complex, first sort array Y and then iterate over each element of X and for each element x in X use binary search to find maximum element y in Y such that x + y <= S.
Binary search here helps in reducing complexity from 2nto 2n/2log(2n/2)which is equivalent to 2n/2n.
Thus our final running time is O(2n/2n).
问题
1.Knapsack
Given a set of N (N≤40) integers each of them is at most 1012 determine the largest sum subset having sum less than or equal S (S≤1018)2.Given a set of n integers where n <= 40. Each of them is at most 1012, determine the maximum sum subset having sum less than or equal S where S <= 1018.
3.4sum
Given A, an array of integers, find out if there are any four numbers in the array that sum up to zero (the same element can be used multiple times). For example given A = [2, 3, 1, 0, -4, -1] a solution is 3 + 1 + 0 - 4 = 0 or 0 + 0 + 0 + 0 = 0.4.Subset Sum Problem