问题是选择算法的一种变体,选择最少数量的项目,使其总和至少为N。例如,您可能希望拥有一个项目列表,其总和为5,000或更多,但不想从输入列表中取出更多项。因此,如果一个数字是5,001,则您的输出列表将包含单个数字。
另一个例子:输入列表{3,4,5,1,2},目标={8}。输出列表将为:{5,3}。
这个问题已经被证明可以使用二进制堆在这个优秀的系列文章中解决;但是当我在Java中实现时,我没有得到期望的输出。我得到了整个输入列表。我无法找到问题的确切原因。这是我的代码;
另一个例子:输入列表{3,4,5,1,2},目标={8}。输出列表将为:{5,3}。
这个问题已经被证明可以使用二进制堆在这个优秀的系列文章中解决;但是当我在Java中实现时,我没有得到期望的输出。我得到了整个输入列表。我无法找到问题的确切原因。这是我的代码;
public class SelectTopSum {
public static void main(String[] args){
int[] arr = {5,2,10,1,33};
int target=33;
System.out.println(Arrays.toString(selectTop(arr, target)));
}
private static int[] selectTop(int[] arr, int sum) {
//get max heap
PriorityQueue<Integer> pq = new PriorityQueue<>(10, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
int runningTot=0;
for (int i : arr) {
if (runningTot<sum) {
runningTot+=i;
pq.add(i);
}
else if (i > pq.peek()) {
runningTot-=pq.remove();
runningTot+=i;
pq.add(i);
}
while (runningTot-pq.peek()>=sum) {
runningTot-=pq.remove();
}
}
//System.out.println("priority queue is "+ pq);
int[] result=new int[pq.size()];
int i=0;
while (!pq.isEmpty()) {
result[i]=pq.remove();
i++;
}
return result;
}
}
[10, 32]
和[1, 32]
都只有2个元素,因此被视为同样好。如果你想返回最小可能的总和,那么这个问题会更加困难,不能用这种方法解决。 - Bernhard Barker