如何計算給定整數列表的確切目標值

有人能指導我在做什麼錯誤嗎？我在過去的4-5天裏進行了大量的研究，每個人都不斷指向子集總和問題或分區問題，對於簡單性原因，我只給出了表現不正確的部分。如何計算給定整數列表的確切目標值

for (Iterator<Activity> iterator = listOfActivities.iterator(); iterator.hasNext();) { 
    Activity currentAct = iterator.next(); 
    if (time + currentAct.getTime() <= 180) { 
     timetable.add(currentAct); 
     time += currentAct.getTime(); 
     iterator.remove(); //removing the current activity once its added to the schedule. 
    } 
} 

time += 60; 
timetable.add(new Activity("Eat Food 20min", "20")); 
// Post Lunch Activities Start here: 
for (Iterator<Activity> iterator = listOfActivities.iterator(); iterator.hasNext();) { 

    Activity currentAct = iterator.next(); 
    if (time + currentAct.getTime() >= 240 && time + currentAct.getTime() <= 480) { 
     timetable.add(currentAct); 
     time += currentAct.getTime(); 
     iterator.remove(); 
    } 
}

來源

2016-12-10 YogendraJ

我們不知道'listOfActivities'包含什麼''時間表'是什麼。請嘗試創建[mcve]。不只是最小的，但*還*完整。 –

如果你的代碼在問題中提供了代碼，而不是作爲外部鏈接，那將會更加清楚。你是否努力通過調試器來完成代碼，並確保你的算法在「紙上」有意義？ –

如果它需要完全等於180，那麼我不能想到線性優化之外的任何算法（我在Java中沒有這樣做）。 –

如果我理解正確的話，你就需要找到加起來爲180，然後將相應的活動添加到Pre-午餐名單，其餘向早報午餐一個列表的數目的子集。

由於在這種情況下檢索相應的活動不是問題，因此您可能需要查看this post，其中描述的算法適合您的問題。
這是一種基本的數字方法，它會嘗試所有可能的組合，然後檢查它們中哪些匹配所需的總和。

來源

2016-12-10 07:51:53 Raven

它總是5分鐘嗎？即使您使用不同持續時間的不同活動？ – Raven

是的，這就是我害怕會發生，因爲你只按列表順序嘗試組合，不採取必要的步驟，並嘗試省略第一/第二/ etc的活動，並嘗試找到其餘的活動。因此，您需要嘗試所有組合，因爲鏈接的算法可以實現它......如果您只是創建一個具有所有活動持續時間的Integer數組，則不應該按照鏈接顯示的方式執行;） – Raven

是的，新的答案實際上解釋了它好一點... – Raven

考慮此輸入：從開始60, 60, 45, 30, 30

您算法進行迭代，並且增加了哪個適合，所以它會增加60（120遺址）的項目，然後60（60具遺體），然後45（15具遺骸）。現在顯然無法填充剩餘的15分鐘，並且完全錯過了添加30和30而不是45的選項。

你所描述的確是一個子集求和問題的實例，它是一個NP-complete problem。這基本上意味着（在這裏簡化很多），你通常必須嘗試所有的可能性 - 沒有直接的方法來達到解決方案。

你的代碼實際上現在做的只是嘗試幾個解決方案，但錯過了很多。爲了以一種簡單的方式解決這個問題，你必須（一旦你經歷了所有的輸入，並沒有完全填充180），刪除最後添加的輸入，嘗試沒有它，等等。但是，研究和實施會更好子集求和問題的動態規劃解決方案，如所描述的在維基百科上。

來源

2016-12-10 08:04:09

然而，這是您需要了解理論以找到有效解決方案的問題之一。所以不要指望找到一個簡單，直接的解決方案來解決您的問題。最簡單的方法是嘗試所有可能的解決方案（也稱爲「回溯」），就像我以及其他人所建議的一樣。 –

如何計算給定整數列表的確切目標值

回答

相關問題