給定N個數組，每個數組貢獻一個元素並添加到k有多少種方式？

說我有N個陣列。這些N陣列在陣列A的陣列N元組有多少這樣的元組T，給定N個數組，每個數組貢獻一個元素並添加到k有多少種方式？

sum = 0 
for i = 0 ... N-1 
    sum += A[i][t[i]] 
sum == k

什麼是解決這個的有效途徑？我能想出的最好的就是列舉所有可能性。

P.S.這不是一個家庭作業問題。我在LeetCode上看到了this，並對一般情況下的解決方案感到好奇。

來源

2016-11-27 Tan Wang

這是子集和問題和NP-complete的變體。 –

@NicoSchertler你能解釋一下嗎？ –

問題如何解決？只需谷歌爲它，你會得到一些算法（例如維基百科文章有幾個）。 –

語言：C++ 限制條件：A [i] [j]> = 0 複雜度：O（N * K）

int A [MAX_N][MAX_N], memo[MAX_N][MAX_K+1]; 

int countWays2(int m, int sum, int N){ 
    if(memo [m][sum] != -1) 
     return memo [m][sum]; 

    if(m == 0) 
     return memo[m][sum] = count(A[0], A[0]+N, sum); 

    int ways = 0; 

    for(int i = 0; i < N; ++i) 
     if(sum >= A[m][i]) 
      ways += countWays2(m-1, sum - A[m][i], N); 

    return memo[m][sum] = ways; 
} 

int countWays(int N, int k){ 
    if(k < 0) return 0; 

    for(int i = 0; i < N; ++i) 
     fill(memo[i], memo[i] + k + 1, -1);  //Initialize memoization table 

    return countWays2(N-1, k, N); 
}

答案是countWays（N，K）

來源

2016-11-28 01:21:14 blu

不鼓勵使用僅限代碼的答案。你應該解釋代碼的作用。至少，定義'k'是什麼。 –

'int A [MAX_N] [MAX_N]'假設代碼是正確的，對於陣列中的10^5個元素，額外的空間複雜度導致38GB範圍內的問題（32位整數）。 –

概念性溶液（可以改善）：

排序每個陣列中的元素
根據所有陣列的絕對最小值移動每個陣列中的元素（abs_min - 要移動所有陣列，您將從所有陣列的每個元素中減去abs_min） - 現在您擁有所有具有非負性元素的陣列，並且您正在搜索一個target_sum = initial_sum - num_arrays*abs_min
設置你的curr_array作爲第一個
二進制文件的target_sum在curr_array位置搜索。您需要考慮curr_array中的所有元素，並在該位置下指數。拿一個這樣的元素，從target_sum中減去它，然後遞歸地用下一個數組重複搜索。

相信（攤銷）的複雜性將是某處的O(num_arrays*N*log(N))其中N是在數組中元素的（最大）數目。

改進的機會：

我有點覺得通過abs_min整體平移陣列是不必要的（只是一種手段，有助於思維）。也許在步驟4遞歸更深一步之前，target_sum可能會被當前數組的最小值移位？
重新排序陣列，使得較短的被認爲是第一意願也許改善性能（較低的數目在遞歸的上水平元件的考慮）[編輯]或也許重新排序的順序依次爲陣列的最小值（以最積極的方式從target_sum中取出）？
採用一種消除/複用初始數組內的重複項的方案可能有所幫助 - 即具有index_key = unique_value和map-value的索引集合的映射。如果特定的元組不是必需的，那麼unique-value-> occurrence_count的映射就足夠了。（如果可以確定存在重複，這可能是有用的 - 例如在數組的值是緊密的範圍內和陣列是相當長 - 束之高閣原理）

[編輯，以表明它是如何工作在{{1, 2, 3}, {42,43, 44, 45, 46, 47}}的示例]

上限=指數的元素嚴格大於所提供的值。如果你想要值小於或等於，取值嚴格低於索引！

零基於索引公約第一陣列中

49目標總和得到的index=3上限（所以在3需要所有索引到被認爲）
第一陣列 - 開始索引= 2/value = 3在第一個數組中，您將在第二個數據庫中尋找target_sum的46。第二個二進制搜索的上限是index=5（並且嚴格看不到），所以從index=4/value = 46（算法刪除47的值）開始。 46是好的，保留，index=3/value=45是不夠的，（沒有一個第3陣列遞歸到它）算法甚至不考慮index=3/value=45。
第一陣列，index=1/value=2，在第二陣列中尋找47的target_sum。獲取上限（二進制搜索）提供index=7（嚴格按照它進行搜索），所以index=6/value=47。 47被保留，46和下方和ALGO切出
第一陣列中向下，index=0/value=1，尋找的48第二陣列中的target_sum。上限再次是7，在index=6/value=47我們得到一個不足的值並終止。

所以，總計：

總二進制搜索：1-在第二第一陣列，3。
測試總成功平等= 2（找到兩個元組）。
測試的不成功的平等總數= 3（直到第二個數組不再提供令人滿意的答案）。（一個用於第一陣列中的每個值）進行
總加法/減法= 3

相反，窮舉掃描會得到：

沒有二進制搜索
總加法= 3 * 6 = 18
總成功平等測試= 2
總未成功平等測試= 16

來源

2016-11-28 01:52:04

這仍然是數組中數量的指數，因爲您必須考慮每個組合。 –

@NicoSchertler「這仍然是數組數量的指數，因爲你必須考慮每個組合。」不。我在排序數組中進行二進制搜索以獲得每個遞歸步驟的總和。如果在任何遞歸步驟中我找不到解決方案，遞歸會終止。例如，當目標總和小於或超過current_array的最大值時，它將立即終止。假設你有一個單一的數組 - 如果數組被排序，找到你的和數有多少步？ –

但是你不知道特定數組的總和。你只知道所有數組的總和。這並不一定均勻分佈。考慮數組''{{1，2，3}，{45，46，47}}'，然後搜索總和'49'。根據你的邏輯，你會打破第一個數組的遞歸，但這是錯誤的。 –

給定N個數組，每個數組貢獻一個元素並添加到k有多少種方式？

回答

相關問題