將鏈接列表等分爲2個子列表

-2

我試圖用相等的總和將鏈接列表分成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}

有人可以提供一些僞代碼來解決這個問題？

這是我到目前爲止想到：

總和鏈表和除法由2
現在的元素，直到你linkedlist1的總和小於總和linkedlist/2不斷將元素推送到linkedlist1。
如果不相等且小於鏈表總和/ 2移動到下一個元素和當前元素可以被推到linkedlist2。

但是，這隻有在元素按特定順序時纔有效。

來源

2014-05-05 NeverGiveUp161

確定誰低估既沒有答案，也沒有downvote的原因。 – NeverGiveUp161

downvoting的一個原因可能是，你沒有顯示你迄今爲止做了什麼... – alain

哈哈酷..至今我做了什麼？你想讓我發佈代碼將鏈表分成兩個子列表嗎？這些元素的順序在增加？這完全不相關。 – NeverGiveUp161

這被稱爲the partition problem。

有幾種方法可以解決這個問題，但我只會提到下面最常見的兩種方法（有關任一方法或其他方法的更多詳細信息，請參閱Wikipedia）。

這可以用dynamic programming方法，它基本上可以歸結爲，對每個元素和值來解決，包括或不包括該元素，並查找是否有一個子集的總和爲相應的值。更具體地講，我們有以下遞推關係：

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)其中n是輸入集中元素的數量，N是輸入集中元素的總和。

的「近似」貪婪的方法（並不一定能找到一個平等和分區）是相當直接的 - 它只是涉及到把每個元素集合中的具有最小總和。這裏是僞代碼：

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-05 15:58:55 Dukeling

將鏈接列表等分爲2個子列表

回答

相關問題