simuyinxi 2018-04-25 06:03 采纳率: 100%
浏览 1314
已采纳

Java数据结构算法问题,求最优解

实际开发中需要解决的问题,我在这里简化成简单的Map:

 Map<String,Integer> map=new HashMap<String,Integer>();
 map.put("tom",78);
 map.put("jerry",42);
 map.put("marry",12);
 map.put("hugh",37);
 map.put("aaron",23);
 map.put("john",40);
 map.put("adam",67);
 map.put("white",43);
 map.put("chris",13);

有这样一个map,key是名字,value是每个人拥有的钱
有一件物品是240元,需要所有人一起凑钱购买,求最优解:
1、第一优先的是人数,凑够钱买物品的人的组合里,人数最少的
2、第二优先的是价格,要求超过240,但是离240最接近的一组,因为从大到小排列一定能得到人数最少的,但是可能会比目标数额大很多,导致找零太多

最后要求返回满足上面两个条件的最优解,也就是这个组合里的所有元素

  • 写回答

10条回答 默认 最新

  • 默默悟问 2018-04-25 08:38
    关注
        public static List<Integer> limitValSubsequence(int[] sequence, int limitValue) {
            List<Integer> retList = new ArrayList<>();
    
            int[] sortSeq = Arrays.copyOf(sequence, sequence.length);
            Arrays.sort(sortSeq);
    
            int sumVal = 0;
            int k = 0;
            for (int i = sortSeq.length - 1; i >= 0; i--) {
                sumVal += sortSeq[i];
                if (sumVal > limitValue) {
                    k = sortSeq.length - i;
                    break;
                }
            }
            if (k == 0) {
                System.err.println("No subsequence math condition to > " + limitValue);
                return retList;
            }
    
            limitValSubsequencePart(sortSeq, k, sequence.length - 1, limitValue, retList);
            return retList;
        }
    
            public static int limitValSubsequencePart(int[] sequence, int count, int right, int limitValue,
                List<Integer> outSeq) 
        {
            outSeq.clear();
            if (count <= 0) return Integer.MIN_VALUE;       //不可选了
            if (right < 0) return Integer.MIN_VALUE;
            int curVal = sequence[right];
            if (limitValue > count * curVal) return Integer.MIN_VALUE;
    
            if (right == 0) {
                if (curVal > limitValue && count == 1) {
                    outSeq.add(curVal);
                    return curVal;
                } else {
                    return Integer.MIN_VALUE;
                }
            }
    
            //if curVal in
            List<Integer> curInSeq = new ArrayList<>();
            int inValue = Integer.MIN_VALUE;    //预设无效
            if (curVal > limitValue && count == 1) {
                inValue = curVal;
                curInSeq.add(curVal);
            } else {
                List<Integer> inSubSeq = new ArrayList<>();
                int subVal = limitValSubsequencePart(sequence, count - 1, right-1, limitValue - curVal, inSubSeq);
                if (subVal == Integer.MIN_VALUE) {//无效
                    inValue = Integer.MIN_VALUE;
                } else {
                    inValue = curVal + subVal;
                    curInSeq.addAll(inSubSeq);
                    curInSeq.add(curVal);
                }
            }
    
            //if curVal not in
            List<Integer> curOutSeq = new ArrayList<>();
            int outValue = limitValSubsequencePart(sequence, count, right-1, limitValue, curOutSeq);
    
            if (inValue == Integer.MIN_VALUE) {
                outSeq.addAll(curOutSeq);
                return outValue;
            } else if (outValue == Integer.MIN_VALUE) {
                outSeq.addAll(curInSeq);
                return inValue;
            } else {
                if (curInSeq.size() < curOutSeq.size()) {
                    outSeq.addAll(curInSeq);
                    return inValue;
                } else if (curInSeq.size() > curOutSeq.size()) {
                    outSeq.addAll(curOutSeq);
                    return outValue;
                } else {
                    if (inValue > outValue) {
                        outSeq.addAll(curOutSeq);
                        return outValue;
                    } else {
                        outSeq.addAll(curInSeq);
                        return inValue;
                    }
                }
            }
        }  
    
      public static void testLimitValArray() {
        final int NUMBER = 150;
        int[] inputs = new int[NUMBER];
        for (int i = 0; i < NUMBER; i++) inputs[i] = i+1;
        int limitValue = NUMBER * 10;
        long startTime = System.currentTimeMillis();
        List<Integer> vals = limitValSubsequence(inputs,  limitValue);
        int sumVal = 0;
        for (int val : vals) sumVal += val;
        long usedTime = System.currentTimeMillis() - startTime;
        System.out.println("testLimitValArray limit:" + limitValue +  ", sum:" + sumVal + ", elems:" + vals + ", usedTime:" + usedTime);
      } 
    
    

    思路和qq_38843185 是一致的。
    testLimitValArray limit:1500, sum:1501, elems:[46, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150], usedTime:9565

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(9条)

报告相同问题?

悬赏问题

  • ¥65 LineageOs-21.0系统编译问题
  • ¥30 关于#c++#的问题,请各位专家解答!
  • ¥15 App的会员连续扣费
  • ¥15 不同数据类型的特征融合应该怎么做
  • ¥15 用proteus软件设计一个基于8086微处理器的简易温度计
  • ¥15 用联想小新14Pro
  • ¥15 multisim中关于74ls192n和DSWPK开关仿真图分析(减法计数器)
  • ¥15 w3wp,exe 中发生未处理的 Microsoft ,NETFramework 异常。
  • ¥20 C51单片机程序及仿真(加减器)
  • ¥15 AQWA | 水动力分析 二阶波浪力