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

Question

实际开发中需要解决的问题，我在这里简化成简单的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最接近的一组，因为从大到小排列一定能得到人数最少的，但是可能会比目标数额大很多，导致找零太多

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

Answer 1

&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;List<Integer>&nbsp;limitValSubsequence(int[]&nbsp;sequence,&nbsp;int&nbsp;limitValue)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<Integer>&nbsp;retList&nbsp;=&nbsp;new&nbsp;ArrayList<>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;sortSeq&nbsp;=&nbsp;Arrays.copyOf(sequence,&nbsp;sequence.length); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Arrays.sort(sortSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;sumVal&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;k&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;sortSeq.length&nbsp;-&nbsp;1;&nbsp;i&nbsp;>=&nbsp;0;&nbsp;i--)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sumVal&nbsp;+=&nbsp;sortSeq[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(sumVal&nbsp;>&nbsp;limitValue)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;=&nbsp;sortSeq.length&nbsp;-&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(k&nbsp;==&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.err.println("No&nbsp;subsequence&nbsp;math&nbsp;condition&nbsp;to&nbsp;>&nbsp;"&nbsp;+&nbsp;limitValue); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;retList; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;limitValSubsequencePart(sortSeq,&nbsp;k,&nbsp;sequence.length&nbsp;-&nbsp;1,&nbsp;limitValue,&nbsp;retList); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;retList; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;int&nbsp;limitValSubsequencePart(int[]&nbsp;sequence,&nbsp;int&nbsp;count,&nbsp;int&nbsp;right,&nbsp;int&nbsp;limitValue, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<Integer>&nbsp;outSeq)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.clear(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(count&nbsp;<=&nbsp;0)&nbsp;return&nbsp;Integer.MIN_VALUE;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//不可选了 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(right&nbsp;<&nbsp;0)&nbsp;return&nbsp;Integer.MIN_VALUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;curVal&nbsp;=&nbsp;sequence[right]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(limitValue&nbsp;>&nbsp;count&nbsp;*&nbsp;curVal)&nbsp;return&nbsp;Integer.MIN_VALUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(right&nbsp;==&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(curVal&nbsp;>&nbsp;limitValue&nbsp;&&&nbsp;count&nbsp;==&nbsp;1)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.add(curVal); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;curVal; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Integer.MIN_VALUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//if&nbsp;curVal&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<Integer>&nbsp;curInSeq&nbsp;=&nbsp;new&nbsp;ArrayList<>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;inValue&nbsp;=&nbsp;Integer.MIN_VALUE;&nbsp;&nbsp;&nbsp;&nbsp;//预设无效 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(curVal&nbsp;>&nbsp;limitValue&nbsp;&&&nbsp;count&nbsp;==&nbsp;1)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inValue&nbsp;=&nbsp;curVal; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curInSeq.add(curVal); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<Integer>&nbsp;inSubSeq&nbsp;=&nbsp;new&nbsp;ArrayList<>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;subVal&nbsp;=&nbsp;limitValSubsequencePart(sequence,&nbsp;count&nbsp;-&nbsp;1,&nbsp;right-1,&nbsp;limitValue&nbsp;-&nbsp;curVal,&nbsp;inSubSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(subVal&nbsp;==&nbsp;Integer.MIN_VALUE)&nbsp;{//无效 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inValue&nbsp;=&nbsp;Integer.MIN_VALUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inValue&nbsp;=&nbsp;curVal&nbsp;+&nbsp;subVal; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curInSeq.addAll(inSubSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curInSeq.add(curVal); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//if&nbsp;curVal&nbsp;not&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<Integer>&nbsp;curOutSeq&nbsp;=&nbsp;new&nbsp;ArrayList<>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;outValue&nbsp;=&nbsp;limitValSubsequencePart(sequence,&nbsp;count,&nbsp;right-1,&nbsp;limitValue,&nbsp;curOutSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(inValue&nbsp;==&nbsp;Integer.MIN_VALUE)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.addAll(curOutSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;outValue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;if&nbsp;(outValue&nbsp;==&nbsp;Integer.MIN_VALUE)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.addAll(curInSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;inValue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(curInSeq.size()&nbsp;<&nbsp;curOutSeq.size())&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.addAll(curInSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;inValue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;if&nbsp;(curInSeq.size()&nbsp;>&nbsp;curOutSeq.size())&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.addAll(curOutSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;outValue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(inValue&nbsp;>&nbsp;outValue)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.addAll(curOutSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;outValue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;outSeq.addAll(curInSeq); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;inValue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp; &nbsp;&nbsp;public&nbsp;static&nbsp;void&nbsp;testLimitValArray()&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;NUMBER&nbsp;=&nbsp;150; &nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;inputs&nbsp;=&nbsp;new&nbsp;int[NUMBER]; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;NUMBER;&nbsp;i++)&nbsp;inputs[i]&nbsp;=&nbsp;i+1; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;limitValue&nbsp;=&nbsp;NUMBER&nbsp;*&nbsp;10; &nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;startTime&nbsp;=&nbsp;System.currentTimeMillis(); &nbsp;&nbsp;&nbsp;&nbsp;List<Integer>&nbsp;vals&nbsp;=&nbsp;limitValSubsequence(inputs,&nbsp;&nbsp;limitValue); &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;sumVal&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;val&nbsp;:&nbsp;vals)&nbsp;sumVal&nbsp;+=&nbsp;val; &nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;usedTime&nbsp;=&nbsp;System.currentTimeMillis()&nbsp;-&nbsp;startTime; &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("testLimitValArray&nbsp;limit:"&nbsp;+&nbsp;limitValue&nbsp;+&nbsp;&nbsp;",&nbsp;sum:"&nbsp;+&nbsp;sumVal&nbsp;+&nbsp;",&nbsp;elems:"&nbsp;+&nbsp;vals&nbsp;+&nbsp;",&nbsp;usedTime:"&nbsp;+&nbsp;usedTime); &nbsp;&nbsp;}testLimitValArray limit:1500, sum:1501, elems:[46, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150], usedTime:9565