given an input array and sum, return the minimum elements need to get sum

Question

The problem is a variation of selection algorithm in selecting the fewest number of items whose sum is at least some value, N. For example you might want to have a list of items whose sum is 5,000 or more, but you don’t want more items than you have to take from an input list. So if one number is 5,001, then your output list will contain a single number.

another example: Input list {3,4,5,1,2} target = {8}. output list will be : {5,3}.

This problem has been shown to solve using binaryHeap in this excellent series of posts; but when I implemented in Java, I do not get the desired the output. I get the entire input list. I am not able to find out the exact cause of the problem. Here is my code;

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

Answer 1

Your comparison is the wrong way around.

PriorityQueue puts the smallest item (based on your comparison) first, and, by saying return o2.compareTo(o1);, you'll treat the largest integer as the smallest, but you need the smallest element needs to be first, not the largest.

You need to change that to:

return o1.compareTo(o2);

(note that I swapped the o1 and o2)

Or, for what it's worth, you can remove the second argument completely from the constructor, as it will then use Integer.compareTo, which will do what you want.