Meet in the middle（折半搜索）

讲解：

https://www.geeksforgeeks.org/meet-in-the-middle/

题目：

5897. 将数组分成两个数组并最小化数组和的差

1755. 最接近目标值的子序列和

956. 最高的广告牌

描述：

「Meet in the middle」是一个搜索技巧，可以在输入很小但是却不足以小到可以使用暴力法算时使用。就像分治法把问题分成两部分，分别解决，然后合并。但是我们并不能像「分治」那样使用「Meet in the middle」，因为「Meet in the middle」没有和原问题一样的子结构。

• 将整数集合划分为A、B两个集合。A、B各含有集合中一半的数；

• 求出集合A中整数所有可能的子集和记录在数组X中。同样求出B中所有可能的子集和并将其存储在数组Y中。因此，数组X和Y的大小最大为$2^{\frac{n}{2}}$；

• 现在合并两个子问题。找到X和Y的组合中和小于或者等于S的组合。

  • 一种方法是迭代数组Y的所有元素以检查数组X的每个元素是否存在这样的组合。

    时间复杂度为：$O((2^{\frac{n}{2}})^{2})=O(2^{n})$

  • 为了简化它，首先将Y进行排序，然后迭代X的每个元素，对X中的每个元素$x$使用二分查找，以找到Y中的最大元素$y$，使$x+y<=S$。

  • 二分查找可以将时间复杂度从$O(2^{n})$降低到$O(2^{\frac{n}{2}}log(2^{\frac{n}{2}}))=O(n2^{\frac{n}{2}})$​。

  • 因此最终时间复杂度为：$O(n2^{\frac{n}{2}})$

例子

给定一个大小为n的整数集合，其中n <= 40。每一个整数都不超过$10^{12}$，确定和小于或等于S(S <= $10^{18}$)的最大子集和。

Input  : set[] = {45, 34, 4, 12, 5, 2} and S = 42
Output : 41
Maximum possible subset sum is 41 which can be 
obtained by summing 34, 5 and 2.

Input  : Set[] = {3, 34, 4, 12, 5, 2} and S = 10
Output : 10
Maximum possible subset sum is 10 which can be 
obtained by summing 2, 3 and 5.

import java.util.*;

/**
 * @Author: merickbao
 * @Created_Time: 2021-10-11 15:52
 * @Description: Meet in the middle
 */

public class MeetInTheMiddle {
	public static void main(String[] args) {
		int[] arr = {3, 34, 4, 12, 5, 2};
		int n = arr.length;
		int[] A = {3, 34, 4};
		int[] B = {12, 5, 2};
		int target_sum = 10;
		HashMap<Integer, HashSet<Integer>> X = new HashMap<>(), Y = new HashMap<>();
		// 计算A B的所有子集可能和
		for (int i = 0; i < 1 << (n / 2); i++) {
			int sum_A = 0, sum_B = 0;
			for (int j = 0; j < n / 2; j++) {
				if (((i >> j) & 1) == 1) {
					sum_A += A[j];
					sum_B += B[j];
				}
			}
			HashSet<Integer> ta = X.getOrDefault(sum_A, new HashSet<>());
			HashSet<Integer> tb = Y.getOrDefault(sum_B, new HashSet<>());
			ta.add(i);
			tb.add(i);
			X.put(sum_A, ta);
			Y.put(sum_B, tb);
		}
		// 进行组合
		// 1. 暴力组合
		int max_sum = -1;
		List<Integer> ans = new ArrayList<>();
		for (Map.Entry<Integer, HashSet<Integer>> en_A : X.entrySet()) {
			int sa = en_A.getKey();
			HashSet<Integer> ia = en_A.getValue();
			for (Map.Entry<Integer, HashSet<Integer>> en_B : Y.entrySet()) {
				int sb = en_B.getKey();
				HashSet<Integer> ib = en_B.getValue();
				if (sa + sb <= target_sum && sa + sb > max_sum) {
					max_sum = sa + sb;
					ans.clear();
					for (int i : ia) {
						ans.add(i);
					}
					for (int i : ib) {
						ans.add(i);
					}
				}
			}
		}
		System.out.println("Output : " + max_sum);
		System.out.print("By : ");
		for (int i : ans) {
			System.out.print(i + " ");
		}
	}
}