给一个任意的集合 随机数字x
取n个数字求和
找到最接近x的数(小于等于)
如 [2,3,5,10,30] x=20 n=3
目标数就是18
其实这个题的本质究竟考察点是什么，这个很重要，楼上qq_16127313的回答有些不得要领。这种类型的面试题如果这样回答，很显然会把面试官噎住。
我们一起分析一下这个问题，这个问题本质上和01背包问题很像，解决01背包问题方式有很多：动态规划和剪枝
动态规划一时间想不出dp推导，所以解决问题算法：深度优先+剪枝，其实这种问题没有什么好的手段，正常的思路就是爆搜，这种时间复杂度是n!，当n等于30的时候代码就废掉了。
不剪枝：
import java.util.HashSet;
import java.util.Set;
/**
* @author yufei.liu
*/
public class Search {
/**
* 带有剪枝的搜素
*
* @param array 数组
* @param searchedSet 当前搜索的集合
* @param n 搜索的层数
* @param N 最终结果
* @param optimum 当前全局最优解
*/
private static void search(int[] array, Set<Integer> searchedSet, int n, int N, Set<Integer> optimum) {
int optimumValue = sum(optimum);
if (searchedSet.size() == n) {
int sum = sum(searchedSet);
if (sum <= N && sum > optimumValue) {
optimum.clear();
optimum.addAll(searchedSet);
}
return;
}
for (Integer item : array) {
if (searchedSet.contains(item)) {
continue;
}
Set<Integer> temp = new HashSet<>(searchedSet);
temp.add(item);
search(array, temp, n, N, optimum);
}
}
private static int sum(Set<Integer> set) {
int sum = 0;
for (Integer item : set) {
sum += item;
}
return sum;
}
public static void main(String[] args) {
int[] array = new int[] {2,3,5,10,30};
int n = 3;
int N = 20;
Set<Integer> set = new HashSet<>();
Set<Integer> optimum = new HashSet<>();
search(array, set, n, N, optimum);
System.out.println(optimum);
}
}
剪枝：
import java.util.HashSet;
import java.util.Set;
/**
* @author yufei.liu
*/
public class Search {
/**
* 带有剪枝的搜素
*
* @param array 数组
* @param searchedSet 当前搜索的集合
* @param n 搜索的层数
* @param N 最终结果
* @param optimum 当前全局最优解
*/
private static void search(int[] array, Set<Integer> searchedSet, int n, int N, Set<Integer> optimum) {
int optimumValue = sum(optimum);
if (searchedSet.size() == n) {
int sum = sum(searchedSet);
if (sum <= N && sum > optimumValue) {
optimum.clear();
optimum.addAll(searchedSet);
}
return;
} else {
// 动态剪枝，如果拿到了10，30，这个时候就没有必要继续搜索了，直接返回
int currentValue = sum(searchedSet);
if (currentValue > N) {
return;
}
}
for (Integer item : array) {
if (searchedSet.contains(item)) {
continue;
}
Set<Integer> temp = new HashSet<>(searchedSet);
temp.add(item);
search(array, temp, n, N, optimum);
}
}
private static int sum(Set<Integer> set) {
int sum = 0;
for (Integer item : set) {
sum += item;
}
return sum;
}
public static void main(String[] args) {
int[] array = new int[] {2,3,5,10,30};
int n = 3;
int N = 20;
Set<Integer> set = new HashSet<>();
Set<Integer> optimum = new HashSet<>();
search(array, set, n, N, optimum);
System.out.println(optimum);
}
}
上面剪枝剪的不够彻底：
1. 如果数组中最小值是2，那么只要currentvalue > N - 2，这种情况下同样没必要搜索了
2. 如果当前最优解是18，currentvalue + arrayMax <= 18，这种情况下没必要继续搜索
所以最终的代码：
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* @author yufei.liu
*/
public class Search {
/**
* 带有剪枝的搜素
*
* @param array 数组
* @param searchedSet 当前搜索的集合
* @param n 搜索的层数
* @param arrayMin 数组最小值
* @param N 最终结果
* @param optimum 当前全局最优解
*/
private static void search(int[] array, int arrayMin, int arrayMax, Set<Integer> searchedSet, int n, int N, Set<Integer> optimum) {
int optimumValue = sum(optimum);
if (searchedSet.size() == n) {
int sum = sum(searchedSet);
if (sum <= N && sum > optimumValue) {
optimum.clear();
optimum.addAll(searchedSet);
}
return;
} else {
// 动态剪枝，如果拿到了10，30，这个时候就没有必要继续搜索了，直接返回
int currentValue = sum(searchedSet);
if (currentValue > N - arrayMin || currentValue + arrayMax <= optimumValue) {
return;
}
}
for (Integer item : array) {
if (searchedSet.contains(item)) {
continue;
}
Set<Integer> temp = new HashSet<>(searchedSet);
temp.add(item);
search(array, arrayMin, arrayMax, temp, n, N, optimum);
}
}
private static int sum(Set<Integer> set) {
int sum = 0;
for (Integer item : set) {
sum += item;
}
return sum;
}
public static void main(String[] args) {
int[] array = new int[] {2,3,5,10,30};
int n = 3;
int N = 20;
Set<Integer> set = new HashSet<>();
Set<Integer> optimum = new HashSet<>();
int arrayMin = Arrays.stream(array).min().getAsInt();
int arrayMax = Arrays.stream(array).max().getAsInt();
search(array, arrayMin, arrayMax, set, n, N, optimum);
System.out.println(optimum);
}
}
public static Integer chooseBestSum(int x, int n, List<Integer> ls) {
int result = -1;
for (int i = 0; i < ls.size(); ++i) {
if (ls.get(i) <= x) {
if (n == 1) {
result = Math.max(result, ls.get(i));
} else {
Integer temp = chooseBestSum(x - ls.get(i), n - 1, ls.subList(i + 1, ls.size()));
if (temp != null) {
result = Math.max(result, ls.get(i) + temp);
}
}
}
}
if (result < 0)return null;
return result;
}