给定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有多少种方式？

回答

相关问题