增量計算揹包

有沒有辦法增量計算揹包問題？任何近似算法？我正試圖在下面的情況下解決這個問題。增量計算揹包

設D是我的數據集，它不是有序的，也不應該是。 D分爲3個子集，即D1，D2和D3。如果需要，D1，D2和D3可以分別訂購。我想爲集合（D1，D2）和（D2，D3）計算單獨的揹包解，但我不想避免計算D2兩次。所以，基本上，我想：

計算（D2）//做一些操作
保存爲中間結果
與D1使用它，並獲得揹包的結果爲（D1，D2）
與D3使用它，並獲得揹包的結果爲（D2，D3）

這樣，在D2中的數據遍歷只需進行一次。有沒有辦法像這樣逐步解決揹包問題？

2016-05-24 Jeyhun Karimov

假設你的意思是0/1揹包問題，是的。如果通常的DP解決方案僅針對D2執行，則記憶的部分結果適合於自舉（D2，D1）或（D2，D3）的DP解決方案。要爲兩者計算解，您需要複製僅D2計算的部分結果。我沒有立即準備回答揹包問題的其他變體。 –

感謝您的回覆。是的，我的意思是0/1揹包問題。據我所知，如果（D2，D1）的組合沒有排序，那麼組合兩個DP解決方案效率不高。在我的情況下，D1和D2是分開排序的，並且集合S =（D2 U D1）或S =（D2 U D3）不一定是分類的。 –

我不確定「排序」是什麼意思。 DP @JohnBollinger指的是不關心元素的順序，所以你不需要對它們進行任何排序 - 你需要做的就是將D2中的元素移到前面。 –

維基百科給出了這樣的僞代碼0/1揹包：https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem

// Input: 
// Values (stored in array v) 
// Weights (stored in array w) 
// Number of distinct items (n) 
// Knapsack capacity (W) 

for j from 0 to W do: 
    m[0, j] := 0 

for i from 1 to n do: 
    for j from 0 to W do: 
     if w[i-1] > j then: 
      m[i, j] := m[i-1, j] 
     else: 
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])

這建立一個2維陣列，使得m[n, W]（最後一行中的最後一個元素）是溶液 - 你上D2運行此。

然後你寫另一個算法，需要這個數組作爲輸入和

沒有做for j ...部分初始化數組
是否for i from D2.count+1 to (D2.count + other.count) do:地方開始另一個不放過。（當在w和v陣列中查找時，你必須調整我）

來源

2016-05-25 17:49:47

增量計算揹包

回答

相關問題