數組列表.get（）不能正常工作

我正在實現一個貪婪算法來解決揹包問題，並且我一直遇到這個我無法弄清楚的問題。數組列表.get（）不能正常工作

public void greedySort() { 
    int curW = 0; 
    Collections.sort(sorted); 
    for(int i = 0; i < sorted.size(); i++) { 
     Entry temp = sorted.get(i); 
     System.out.println("Index: " + temp.index + "Ratio: " + temp.ratio); 
    } 
    System.out.println("Sorted size: "+sorted.size()); 
    while(sorted.size() > 0 && curW < maxW) { 
     Entry temp = sorted.get(0); 
     if(curW + temp.weight <= maxW) { 
     ret.add(temp); 
     curW += temp.weight; 
     } 
     sorted.remove(0); 
    } 
}

當我運行

Entry temp = sorted.get(0);

我得到一個IndexOutOfBoundsException異常，即使在for循環後的Collections.sort（排序）將通過「分類」正確迭代並打印出所有的值正確的順序。我究竟做錯了什麼？此外，如果您在此代碼中看到我的算法設計出現任何錯誤，請告訴我這些信息。

編輯：添加了Sorted.size println。它會打印20個，因爲它應該。 Sorted是一個按其值/重量比排序的揹包條目的ArrayList。排序是不是空的，這裏是通過它

Index: 14 Ratio: 14.0 
Index: 0 Ratio: 3.1379310344827585 
Index: 15 Ratio: 2.7 
Index: 4 Ratio: 1.7555555555555555 
Index: 17 Ratio: 1.72 
Index: 19 Ratio: 1.4210526315789473 
Index: 8 Ratio: 1.3333333333333333 
Index: 18 Ratio: 1.2195121951219512 
Index: 11 Ratio: 1.2 
Index: 1 Ratio: 0.9230769230769231 
Index: 9 Ratio: 0.9230769230769231 
Index: 6 Ratio: 0.8636363636363636 
Index: 2 Ratio: 0.8591549295774648 
Index: 12 Ratio: 0.6530612244897959 
Index: 5 Ratio: 0.647887323943662 
Index: 16 Ratio: 0.6111111111111112 
Index: 7 Ratio: 0.5876288659793815 
Index: 10 Ratio: 0.3508771929824561 
Index: 13 Ratio: 0.34831460674157305 
Index: 3 Ratio: 0.15 
Sorted size: 20 
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0

排序在這裏創建爲前面的評論者指出的使用給予函數值由駕駛員

public void Greedy(int[] val, int[] weight, int maxVal) { 
    final long startTime = System.currentTimeMillis(); 
    GreedyAlgorithm alg = new GreedyAlgorithm(); 
    alg.sorted = new ArrayList<Entry>(); 
    alg.ret = new ArrayList<Entry>(); 
    alg.maxW = maxVal; 
    for(int i = 0; i < val.length; i++) { 
    Entry newE = new Entry(); 
    newE.index = i; 
    newE.value = val[i]; 
    newE.weight = weight[i]; 
    newE.ratio = ((double)newE.value)/((double)newE.weight); 
    alg.sorted.add(newE); 
    } 
    alg.greedySort(); 
    final long endTime = System.currentTimeMillis(); 
    System.out.println("Total execution time: " + (endTime - startTime)); 
}

來源

2015-06-03 Evan Cooper

什麼是「排序」？ – HyperNeutrino

您不斷移除循環中的第一個元素。這可能會使列表一度爲空。 – Thilo

不知道您的算法，但在循環檢查時添加'&& sorted.size（）> 0'。 –

運行20值輸入文件後的輸出，你繼續刪除ArrayList中的第一個元素。在迭代所有20個元素時，您已經刪除了ArrayList中的所有內容。

所以，只要確保在列表爲空時結束循環。改變你的條件：

while(sorted.size() > 0 && curW < maxW) { 
    // Put this print line inside the loop to debug. 
    System.out.println("Sorted size: "+sorted.size()); 
    Entry temp = sorted.get(0); 
    if(curW + temp.weight <= maxW) { 
     ret.add(temp); 
     curW += temp.weight; 
    } 
    sorted.remove(0); 
}

來源

2015-06-03 01:43:27 hungryghost

重新編譯並嘗試添加，沒有任何更改。這將有助於代碼最終執行。 –

要進行調試，請在while循環內添加println以顯示sorted.size（）。排序肯定會被清空。這是例外。 – hungryghost

顯然我的IDE導致了某種問題，它最近有點不穩定。重新啓動後，我打開文件並運行它們，錯誤消失了。

感謝Thilo和hungryghost，在重啓任何一種方式後，while循環問題都會出現。

來源

2015-06-03 01:56:31

數組列表.get（）不能正常工作

回答

相關問題