qq_43667812
2018-11-11 14:22
采纳率: 50%
浏览 447
已采纳

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

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

            如 [2,3,5,10,30]  x=20  n=3
            目标数就是18
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

  • 玄尺 2018-11-11 16:36
    最佳回答

    其实这个题的本质究竟考察点是什么,这个很重要,楼上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);
        }
    
    }
    
    评论
    解决 无用
    打赏 举报
查看更多回答(1条)

相关推荐 更多相似问题