问题:给定一个总和为 0 的数组,找到其最大分区数,使得所有分区的总和分别为 0。
示例:
我的解决方案:
我从初始列表中找到总和为 0 并且是真子集的任何子集(下面代码中的函数
f
发现任何子集)。它的脱节也是一个答案。然后我对我发现的结果运行相同的算法。
def return_n_subsets(balances):
balances.sort()
n = len(balances)
if n == 0:
return 0
@cache
def f(sp, cur_sum):
if sp == len(balances):
return None
if balances[sp] == -cur_sum:
return [balances[sp]]
if cur_sum > 0: #early stop since there would be only positive numbers from here on
return None
#include sp
out1 = f(sp+1, cur_sum + balances[sp])
if out1 is not None:
out1 = out1[:] #############################
out1.append(balances[sp])
if len(out1) != len(balances): #condition to not return the input itself
return out1
#dont include sp
out2 = f(sp+1, cur_sum)
if out2 is not None:
out2 = out2[:] ##############################
return out2
return None
sub1 = f(0,0)
if sub1 is None:
return 1
[balances.remove(i) for i in sub1]
subsets = [sub1, balances]
out = 2
while True:
new_subsets = []
for balances in subsets:
balances.sort()
f.cache_clear()
sub1 = f(0, 0)
if sub1 is not None:
[balances.remove(i) for i in sub1]
new_subsets.append(balances)
new_subsets.append(sub1)
else:
out += 1
if len(new_subsets) == 0:
break
subsets = new_subsets
return out
我的时间复杂度计算:
我正在遍历原始列表的每个子集,并且在每次迭代时我还创建输出列表的副本(代码中的行后面有很多哈希值)。这是 Nx2^N。然后我得到 2 个大小为 N/2 的子集,然后运行 2xN/2x2^(N/2)。然后我运行 4xN/4x2^(N/4) 等等。
总体时间复杂度:O(Nx2^N + Nx2^(N/2) + Nx2^(N/4) ...) = O(Nx(2^N + 2^(N/2) + 2^( N/4) ...)) = O(Nx2^N)
您的问题包含 3-分区问题 几乎是一个特例。也就是说,我们能否将一个集合分成 3 个集合,每个集合的总和相同。这是强 NP 完全的。这意味着它不仅是 NP 完全的,而且不存在伪多项式近似。因此,您不应期望比指数最坏情况更好。
我没有详细分析你的复杂性,但最终结果听起来很合理。
现在我们可以更快吗?最坏的情况下?不,在实践中?让我们拿出我的旧备忘单。
这是我将如何做的概述。
(abs(element), count_negatives, count_positives)
。所以对于你的例子来说没有0。排序后我们得到
[5, -4, 4, -3, -2]
。朴素的下界将是 2
(我们可以将 -4, 4
配对,然后除以剩余的 3
)。 A* 搜索将立即验证这是否有效。
不幸的是有两个问题:
我正在编写这两个库,但它们是中型大型项目,因此无法承诺何时完成。
但这应该让我们知道可以优化多少。