我有一个数组,我想将它分成两部分,使它们的总和相等,例如 [10, 30, 20, 50]
可以拆分成[10, 40] , [20, 30]
.两者的总和为 50。这本质上是分区算法,但我希望检索子集而不仅仅是确定它是否可分区。因此,我继续执行以下操作:
更新:更新脚本以处理重复
from collections import Counter
def is_partitionable(a):
possible_sums = [a[0]]
corresponding_subsets = [[a[0]]]
target_value = sum(a)/2
if a[0] == target_value:
print("yes",[a[0]],a[1:])
return
for x in a[1:]:
temp_possible_sums = []
for (ind, t) in enumerate(possible_sums):
cursum = t + x
if cursum < target_value:
corresponding_subsets.append(corresponding_subsets[ind] + [x])
temp_possible_sums.append(cursum)
if cursum == target_value:
one_subset = corresponding_subsets[ind] + [x]
another_subset = list((Counter(a) - Counter(one_subset)).elements())
print("yes", one_subset,another_subset)
return
possible_sums.extend(temp_possible_sums)
print("no")
return
is_partitionable(list(map(int, input().split())))
示例输入和输出:
>>> is_partitionable([10,30,20,40])
yes [10, 40] [30, 20]
>>> is_partitionable([10,30,20,20])
yes [10, 30] [20, 20]
>>> is_partitionable([10,30,20,10])
no
我实际上是在存储相应的值,这些值是为在 corresponding_subsets
中获取值而添加的.但是,由于 a
的大小增加,很明显 corresponding_subsets
会有太多的子列表(等于 possible_sums
中的元素数)。有没有更好/更有效的方法来做到这一点?
最佳答案
虽然这仍然是一个难题,但您可以尝试以下方法。我假设有 n
元素,它们存储在名为 arr
的数组中(我假设基于 1 的索引)。让我们组成两个团队 A
和 B
,这样我想在团队 A
之间划分 arr
的元素和 B
使得两个团队中的元素总和相等。 arr
的每个元素都可以选择加入团队 A
或团队 B
。假设一个元素(say ith element)去团队 A
我们用 -a[i]
表示它,如果它去团队 B
我们让它成为a[i]
。因此,在将每个元素分配给一个团队后,如果总和为 0
,我们的工作就完成了。我们将创建 n
集(它们不存储重复项)。我将使用示例 arr = {10,20,30,40}
。按照以下步骤操作
set_1 = {10,-10} # -10 if it goes to Team A and 10 if goes to B
set_2 = {30,-10,10,-30} # four options as we add -20 and 20
set_3 = {60,0,20,-40,-20,-60} # note we don't need to store duplicates
set_4 = {100,20,40,-40,60,-20,-80,0,-60,-100} # see there is a zero means our task is possible
现在你所要做的就是从最后一个集合中的 0
回溯,看看第 i 个元素 a[i]
是否被添加为 a[ i]
或 -a[i]
,即。是否添加到团队 A
或 B
。
编辑
回溯例程。所以我们有 n
个集合,从 set_1
到 set_n
。让我们创建两个列表 list_A
来推送属于团队 A
的元素,类似地 list_B
。我们从 set_n
开始,因此使用初始值为 n
的变量 current_set
。此外,我们关注最后一个列表中的元素 0
,因此使用变量 current_element
初始值为 0
。按照下面代码中的方法(我假设所有集合 1 到 n
都已经形成,为了方便我将它们存储为列表列表,但你应该使用集合数据结构)。此外,下面的代码假定在最后一个列表中看到了 0
,即。我们的任务是可能的。
sets = [ [0], #see this dummy set it is important, this is set_0
#because initially we add -arr[0] or arr[0] to 0
[10,-10],
[30,-10,10,-30],
[60,0,20,-40,-20,-60],
[100,20,40,-40,60,-20,-80,0,-60,-100]]
# my array is 1 based so ignore the zero
arr = [0,10,20,30,40]
list_A = []
list_B = []
current_element = 0
current_set = 4 # Total number of sets in this case is n=4
while current_set >= 1:
print current_set,current_element
for element in sets[current_set-1]:
if element + arr[current_set] == current_element:
list_B.append(arr[current_set])
current_element = element
current_set -= 1
break
elif element - arr[current_set] == current_element:
list_A.append(arr[current_set])
current_element = element
current_set -= 1
break
print list_A,list_B
关于python - 如何在分区算法中检索子集?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39514839/