用於乘法的揹包算法

我有一組N數字，每個數字都附加了一些成本，問題是選擇所有可能的數字集合作爲列表，使得它們的產品小於某個數字M，按照到成本的總和。用於乘法的揹包算法

如： - 該組數字是

(number, costOfThatNumber) : {(90, 10) , (80, 20), (60, 40), (40, 60), (15, 85)},

和產品必須小於，Prod <= 1000，

可能的解決方案是： -

[Solution 1 :- {(15, 85), (40, 60)} :- Product = 600 (which is less than, 1000), cost = 85 + 60 = 145] 
[Solution 2 :- {(15, 85), (80, 20)} :- Product = 900 and cost = 105]

所以名單而成， {Solution2, Solution1}。

PS： -

這是不是一個功課問題，這是在採訪中問道。我被問到只有算法，我只能說，它看起來有點類似於揹包問題，但乘法。
請原諒，如果我無法正確解釋問題。

來源

2012-05-10 user1045047

如果不是最佳解決方案，即使有人給我一個蠻力算法，我也會感激，我甚至可以找到一種方法來選擇所有可能的子集。 – user1045047

你的例子錯了嗎？ 15 * 80不是900 ...應該不是（15,85），（60,40）？ – svinja

我假設可以將問題簡化爲揹包問題。

注意

x1 * x2 * ... * xn <= M <-> 
log(x1*x2*...*xn) <= log(M) <-> 
log(x1) + log(x2) + ... + log(xn) <= log(M)

因此，找到使用揹包的最佳解決方案可以做到：

weight'(item) = log(weight(item)) 
value(item) = value(item) 
M' = log(M) 
run Knapsack on the items with weight', value, M'

更多的工作將需要獲得所有可行的解決方案，而不僅是最優的，但因爲有那些指數（2^n if M = infinity），我懷疑甚至有僞多項式的解決方案。

一個非高效的解決方案是創建power set（包含所有可能的集合的集合），並檢查它們中的每一個的可行性和它的價值，並根據它們的價值在有序集合中存儲可行解。 This post解釋如何獲得功率設置。

來源

2012-05-10 18:28:50 amit

這是少數幾種情況之一，其中最優算法當然是指數運行時間（以獲得所有解），因爲最壞情況下的輸出大小是指數。在所有情況下，輸出大小都是複雜度的下限。如果您需要計算並填充內存中的X個位置，則需要X個步驟才能完成此操作，但無論如何計算每個結果的方式都無法解決。 – svinja

如上所述，這不是揹包問題。只需按遞增順序對這些對進行排序，從一開始就選擇，直到達到產品限制，然後根據成本進行重新排序。如上所述，並不要求總成本應低於任何閾值或限制，因此最佳解決方案就是選擇具有最小第一個元素的對。

來源

2012-05-11 06:22:52

用於乘法的揹包算法

回答

相關問題