simuyinxi
simuyinxi
2018-04-25 02:45
采纳率: 100%
浏览 1.2k
已采纳

java数据结构算法问题,几个数相加得到满足条件的最小和

我假设一种情况吧:
int[] arr={35,47,26,18,14,35,98,52,48,23,49,32}
假如我需要一个数:360
我现在想知道,上面数组里面的哪几个数相加能大于350
但是所有加起来大于350的组合里数据个数是最少的
需要算法优化,遍历所有情况耗费太大

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • yszd2017
    yszd2017 2018-04-25 02:52
    已采纳

    将 数组 int[] arr={35,47,26,18,14,35,98,52,48,23,49,32} 进行 由大到小的排序,
    那么 从头遍历 累计,累加和 第一大于350 的数据 即符合条件的数据。

    点赞 评论
  • a718089112
    a718089112 2018-04-25 02:54

    排序数据,循环数据个数 按照数据个数二分查找

    点赞 评论
  • A289048093
    李朝 2018-04-25 03:01
       思路:要个数最少,所以需要最大的数相加才是最少的个数,先排序,然后在做累加,判断,代码如下:
    
        Arrays.sort(arr);
            int total = 0;
            List<Integer> res  = new ArrayList<>();
            for(int i=arr.length-1;i>=0;i--){
                res.add(arr[i]);
                if((total += arr[i])>350){
                    break;
                }
            }
            System.out.println(total);
            System.out.println(res);
    
    点赞 评论

相关推荐