給出一個輸入數組，總之，返回最小的元素需要得到總和

的問題是selection algorithm在選擇最少數量的項目，其總和至少爲某個值的變化，N.例如，你可能希望有一個其中總數爲5,000或更多的項目列表，但是您不需要比輸入列表中更多的項目。所以如果一個數字是5,001，那麼你的輸出列表將包含一個數字。給出一個輸入數組，總之，返回最小的元素需要得到總和

另一個例子：Input list {3,4,5,1,2} target = {8}. output list will be : {5,3}。

此問題已被證明在這個excellent series of posts使用binaryHeap解決; 但是當我在Java實現，我沒有得到期望的輸出。我得到了整個input list。我無法找出問題的確切原因。這是我的代碼;

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

來源

2014-02-19 brain storm

您的比較是錯誤的。

PriorityQueue放最小項目（根據您的比較）第一，並說return o2.compareTo(o1);，你會好好對待的最大整數爲最小，但你需要的最小元素必須是第一，不最大的。

您需要更改到：

return o1.compareTo(o2);

（請注意，我換了o1和o2）

或者，對於它的價值，你可以從構造完全刪除第二個參數，因爲它會使用Integer.compareTo，這將做你想要的。

來源

2014-02-19 23:23:58 Dukeling

但我不希望最小的項目是在堆頂部，我想在上面最大的，所以我可以將其刪除..？ –

仍然適用於一些，但不適用於所有輸入。 '例如：int [] arr = {5,1,10,32}; int target = 33;給出[10，32]'，而它應該給[32.1] –

反覆刪除*最小*如果這樣做會導致仍然過的總和。然後堆中剩下的是最大的元素，總和至少是總和（也是元素的最小數量）。然後你返回這些。考慮你的代碼示例 - 首先將所有元素添加到堆中，然後刪除1,2,5和10，所以我們剩下33個，然後返回。 – Dukeling

給出一個輸入數組，總之，返回最小的元素需要得到總和

回答

相關問題