一个java 题目,大神帮帮我~~

给一个任意的集合 随机数字x
取n个数字求和
找到最接近x的数(小于等于)

            如 [2,3,5,10,30]  x=20  n=3
            目标数就是18
0

2个回答

其实这个题的本质究竟考察点是什么,这个很重要,楼上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);
    }

}
3
weixin_37893887
玄尺 回复qq_43667812: 是的,这是我的问题。应该使用list才对
9 个月之前 回复
qq_43667812
qq_43667812 如果数组[2,3,10,10,30] x= 22 n=3 最优解应该是 [2,10,10] set的话就不会有两个10啊
9 个月之前 回复
weixin_37893887
玄尺 回复qq_43667812: 只要数组是非负数就可以,重复不重复没啥关系
9 个月之前 回复
qq_43667812
qq_43667812 如果原数组有重复值呢。。在网上找到原题了 ,答案贴在下面 看不懂。。放弃了
9 个月之前 回复
qq_43667812
qq_43667812 多谢大佬费心~ 没想到这么难。。
9 个月之前 回复
caozhy
贵阳挖掘机马善福,自备车辆专业挖游泳池 赞,这么晚还没睡?
9 个月之前 回复
    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;
        }
0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!