simuyinxi 2018-04-25 06:03 采纳率: 100%

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

`````` 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("white",43);
map.put("chris",13);
``````

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) {
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;
} 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;
}
}

//if curVal not in
List<Integer> curOutSeq = new ArrayList<>();
int outValue = limitValSubsequencePart(sequence, count, right-1, limitValue, curOutSeq);

if (inValue == Integer.MIN_VALUE) {
return outValue;
} else if (outValue == Integer.MIN_VALUE) {
return inValue;
} else {
if (curInSeq.size() < curOutSeq.size()) {
return inValue;
} else if (curInSeq.size() > curOutSeq.size()) {
return outValue;
} else {
if (inValue > outValue) {
return outValue;
} else {
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

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 java 这种树形框吗
• ¥40 找同学帮敲Python代码
• ¥15 MYSQL 订单的商品明细重复计算问题
• ¥15 微信实时共享位置修改
• ¥100 TG的session协议号转成直登号号后客户端登录几分钟后自动退出设备
• ¥50 共模反馈回路的小信号增益
• ¥15 arduino ssd1306函数与tone函数放歌代码不兼容问题
• ¥70 0.96版本hbase的row_key里含有双引号，无法deleteall
• ¥15 诊断性META分析合并效能的检验
• ¥15 请问abb根据色块判断奇偶数并根据批次号放入仓储