將一個數組劃分爲最佳的不等於總和子列表

Question

嗨，我試圖找到什麼樣的數據結構算法，我必須在這個問題中使用。我有兩個數組，一個包含產品重量，另一個包含成本。我必須將產品重量分成最佳數量的包裝，每個包裝具有相同的重量，單個產品的成本或總產品的成本在分割後不應超過每個包裝300美元。

例：權重= [1000,500,500]成本= [150,75,75]

我們並不需要把它們分爲多個包，因爲所有產品的總成本不超過$ 300。所以我們可以把它們作爲一個包裹發送。

例：權重= 1000，500，500]成本= [200，100，100]

現在的所有產品的成本超過$ 300，所以我們必須把它們分爲具有相等的權重包而且每個成本不應該超過300美元。

我們可以把它們分成兩個包，一個包含1000克，另一個包含1000克（500 + 500），成本不會超過300美元。

我不是在尋找代碼或東西。我只需要一個關於如何分割多個包的東西的提示或算法。

Answer 1

找到具有給定權重的單個子集是NP難的。如果你有某種方法可以識別給定重量的所有子集，並且其成本低於300美元，那麼你需要解決一個確切的覆蓋問題，這是一般的NP難題。所以你不能指望在最壞的情況下找到任何小於指數複雜度的算法。

但我會嘗試在這裏是這樣的：

let W = total weight of all packages 
let N = total number of packages 
for k = 1, 2, 3, ..., N 
    find all subsets of packages with weight W/k and cost less than $300 
    if there's an exact cover: stop with solution. 

您可以採用動態規劃假設不同重量和成本的數權重的子集和成本足夠小。您可以使用跳舞鏈接算法找到確切的封面。