數字子集的和

假設我有一個數字'n'和一個數字表。我想選擇表格中的四個數字，並且這四個數字的總和與n最接近。給定表格的長度'L'，它必須經歷的組合的數量是（6 * L + 11 * L^2 + 6 * L^3 + L^4）/ 24。數字子集的和

ex。說我有可變

n = 100

和鑑於這一列表中，四個至n最接近組合該組數字中

t = {86, 23, 19, 8, 42, 12, 49}

的是49 + 23 + 19 + 8 = 99。

用盡可能少的計算次數做這件事的最佳方法是什麼？

來源

2013-03-26 Waffle

[？揹包（http://en.wikipedia.org/wiki/Knapsack_problem） – 2013-03-26 19:32:28

在正常揹包問題您選擇的物品的最大數量不受限制，而在您的問題中似乎有四個限制。我仍然會使用與0/1揹包（動態編程）相同的方法。通過這種方法，你可以用'O（4nL）'來解決它，只要你獲得超過幾件物品，速度就會快很多。 – Yexo 2013-03-26 19:56:17

如果窮舉搜索算法速度太慢，請嘗試**分支並綁定**，這樣您就可以忽略大量子集而不嘗試它們。閱讀第13章http://www.statslab.cam.ac.uk/~rrw1/mor/s2010a4.pdf – 2013-03-26 21:09:21

這看起來像「子集和」（見：http://en.wikipedia.org/wiki/Subset_sum_problem）的變化問題，這是衆所周知的是NP完全，所以很遺憾很可能不會有根本的是，在最壞的任何巧妙的算法-case將運行速度快於指數的項目數量。

如果沒有太多的項目需要檢查（大約10左右），您可以嘗試深度優先搜索修剪分支儘快。

如果有更多的項目可能檢查最有可能而不是尋找最佳的解決方案，你可能會更好地嘗試找到一個比較好的近似值。

來源

2013-03-26 19:37:15 mikyra

他的問題受到限制。有一個小數的O（n^4）解決方案，只是列舉了每個大小最多爲4的子集。 – 2013-03-26 20:52:08

你是對的。似乎我錯過了有固定數量的項目。 – mikyra 2013-03-26 21:18:38

假設所有的數字是正整數，這是可以做到的Yexo指出：

local n = 100 
local t = {86, 23, 19, 8, 42, 12, 49} 
local max_terms = 4 
-- best[subset_size][terms][k] = {abs_diff, expr} 
local best = {[0] = {}} 
for k = 1, n do best[0][k] = {k, ''} end 
for terms = 0, max_terms do best[terms] = best[0] end 
for subset_size = 1, #t do 
    local new_best = {} 
    for terms = subset_size == #t and max_terms or 0, max_terms do 
     new_best[terms] = {} 
     for k = subset_size == #t and n or 1, n do 
     local b0 = best[terms][k] 
     local diff = k - t[subset_size] 
     local b1 = terms > 0 and (
      diff > 0 and { 
       best[terms-1][diff][1], 
       best[terms-1][diff][2]..'+'..t[subset_size] 
      } or {math.abs(diff), t[subset_size]} 
     ) or b0 
     new_best[terms][k] = b1[1] < b0[1] and b1 or b0 
     end 
    end 
    best = new_best 
end 
local expr = best[max_terms][n][2]:match'^%+?(.*)' 
print((loadstring or load)('return '..expr)()..' = '..expr) 

-- Output 
99 = 23+19+8+49

來源

2013-03-26 20:46:38

'對於k = 1，n do'看起來甚至比通過每種可能的組合效率更低。 n可能是1000萬。 – Waffle 2013-03-26 21:11:37

有沒有辦法做到這一點，在計算結果所採取的工作不依賴於n，這可能是任何數字？ – Waffle 2013-03-27 00:32:18

如果這組數字的大小是1000，那麼我的解決方案需要大約420億次迭代。我需要一個解決方案，可以用盡可能少的計算來處理很多數字。 – Waffle 2013-03-27 12:13:16

數字子集的和

回答

相關問題