-2

我正在尝试将链接列表划分为 2 个总和相等的子列表。这些子列表不需要包含连续的元素。

我有一个链表作为

Eg.1
LinkedList={1,7,5,5,4}
should be divided into
LinkedList1={1,5,5}
LinkedList2={7,4}

两者的元素总和都与 11 相同。

Eg.2
LinkedList={42,2,3,2,2,2,5,20,2,20}
This should be divided into two list of equal sum i.e 50.
LinkedList1={42,3,5}
LinkedList2={2,2,2,2,20,2,20}

有人可以提供一些伪代码来解决这个问题吗？

这是我到目前为止的想法：

  1. 将链表的元素相加并除以 2。

  2. 现在直到您的linkedlist1 的总和小于linkedlist/2 的总和，继续将元素推入linkedlist1。

  3. 如果不等于且小于linkedlist sum/2，则移动到下一个元素，当前元素可以推送到linkedlist2。

但这仅在元素按特定顺序排列时才有效。

4

1 回答 1

1

这就是所谓的分区问题。

有几种方法可以解决这个问题，但我只会在下面提到最常见的 2 种（有关任何一种方法或其他方法的更多详细信息，请参见Wikipedia ）。

这可以通过动态编程方法来解决，该方法基本上归结为对于每个元素和值，包括或不包括该元素，并查找是否存在与相应值相加的子集。更具体地说，我们有以下递归关系：

p(i, j)是True如果和的子集{ x1, ..., xj }，i否则False。

p(i, j)是True如果p(i, j − 1)是True或者如果p(i − xj, j − 1)是True
p(i, j)不是False

然后p(N/2, n)告诉我们是否存在子集。

运行时间是输入集中元素的数量，是输入集中O(Nn)元素的总和。nN

“近似”贪心方法（不一定找到等和分区）非常简单——它只涉及将集合中的每个元素放在总和最小的地方。这是伪代码：

INPUT:  A list of integers S
OUTPUT: An attempt at a partition of  S into two sets of equal sum
1  function find_partition( S ):
2     A ← {}
3     B ← {}
4     sort  S in descending order
5     for i in S:
6        if sum(A) <= sum(B)
7           add element i to set A
8        else
9           add element i to set B
10    return {A, B}

运行时间为O(n log n)。

于 2014-05-05T15:58:55.463 回答