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最接近的一组，因为从大到小排列一定能得到人数最少的，但是可能会比目标数额大很多，导致找零太多
最后要求返回满足上面两个条件的最优解，也就是这个组合里的所有元素
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
1，把所有的value取出来，用9层for循环 for（int i =0 ,i < =1 ,i++） 判断结束条件为 sum = 78i+42j+12x+。。。。 > =240;
2, 把每种方式取出来，做比较先去人数最少的 就是变量0最多的一个。如果相等比较钱数最小的，
如果你这个最近的一组得有一个区间来判断，如果为240-260直接，或者260-280之间这种，就可以判断一下钱满不满足条件，不满足的就取下一个
。大致的想法就这样，具体实现还得自己根据需求优化
分析一下哈：这个题的两个需求，一个是人要少，还有一个是钱要刚好多出一点点或者是正好。
对于第一个要求，从大到小排然后往上加就好了，第二个需求就比较难弄了，要求是在第一个基础上，从上往下捋顺，具体有点儿复杂，如果条数多的话，值得好好想一想写一写。
我初步的思路就是先用第一个条件，卡出那个个数。然后用这个个数来对钱数的组合进行限制。
比方说个数是4，就给要选出的4个数，排上号1234，规定1>=2，2>=3,3>=4;mark
先排序得到满足第一个条件的人数K，接下来就是一个最接近K-SUM问题，不过只取超过的SUM，大致思路就是这样。
//获取最大个数方法就不写了。例子是3个数，思路是获取任意3个数据元素组合 结果存到map中 最后比较map结果，完全按照需求啊 求分
int a[] = {60,55,50,45,40,30,20,15};
int target = 120 ;
//首先获取最大个数
int minNum = 3;
Map<String,Integer> map = new HashMap<String,Integer>();
//取出数组下任意元素组合下标
for(int i=0;i<=(a.length-minNum+1);i++){
for(int j=0;j<a.length;j++){
String flag = "";
int maxIndex = 0;
int total = 0;
for(int k=0;k<minNum;k++){
if((k+1) == minNum){
flag = flag + (k+j+i)+",";
maxIndex = k+j+i;
if(maxIndex >= a.length){
break;
}
total = total + a[(k+j+i)];
}else{
flag = flag + (k+i)+",";
total = total + a[(k+i)];
}
}
if(maxIndex >= a.length){
break;
}
System.out.println(flag + "======" + total);
map.put(flag, total);
}
}
//对map结果进行120匹配即可
几点小建议，也不一定正确：
1、基础数据的集合，即map，最好事先用TreeMap，因为容器内元素天然有序，对我们后面的计算会减少很多时间。
2、得到一个有序集合后，先从大到小取到满足条件的最少人数。
3、剩下的就是遍历，比较了；
ps：这种问题肯定避免不了遍历和递归这种操作，最优方案无非是在时间复杂度和空间复杂度上做权衡，如果是实际业务上的问题，再结合一些现实因素；
如果是线上的问题，实在不行引入一些并行计算的东西，也不失为解决方案~~~
这不就是典型的动态规划题，为什么上面的搞这么绕
接上上面的，拿到个数以后，再把数据分一分再遍历，
我拿你给的数据来试试。
求出类似这么一个平均数的东西，240÷5=48
然后用差值算。给它们分开。
public void test4() {
Map map = new HashMap();
String[] keys = {"tom","jerry","marry","hugh","aaron","john","adam","white","chris"};
int[] values = {78,42,12,37,23,40,67,43,13};
Arrays.sort(values);
System.out.println(Arrays.toString(values));
int sum = 0;
for(int i = values.length-1;i>=0;i--) {
sum+=values[i];
map.put(keys[i], values[i]);
if(sum>=240) {
sum -= values[i];
break;
}
}
for (int i = 0; i < values.length; i++) {
if(sum+values[i]>=240) {
sum+=values[i];
map.put(keys[i], values[i]);
System.out.println(sum);
System.out.println(map);
break;
}
}
}