# 如何降低解决子集优化问题的时间复杂度？

##### 问题描述投票：0回答：1

``````const exampleQueue = [
{a: 10, b: 4},
{a: 7, b: 10},
{a: 3, b: 6},
{a: 1, b: 4},
{a: 1, b: 1},
]
const mappedToA = [10, 7, 3, 1, 1] // does not meet the threshold
const firstAttempt = [10, 7, 3, 1, 0]
const secondAttempt = [10, 7, 3, 0, 1]
const thirdAttempt = [10, 7, 3, 0, 0]
const fourthAttempt = [10, 7, 0, 1, 1]
// ...
``````

algorithm optimization data-structures subset big-o
##### 1个回答
0

1. 动态规划。增量构建数据结构以避免重复重新计算。这将许多问题（包括子集和之类的问题）从指数问题转变为伪多项式问题。在实践中，这通常是可行的。
2. 最佳边缘。我们不需要保留所有的可能性。只是那些可能导致某种最佳权衡的因素。
3. 链接列表。很少有人意识到这一点，但动态编程可以有效地构建链表数据结构，从而提取最佳解决方案。关键是当你回溯选择时，两个不同的链表可以合并。因此，保留当前所有最佳可能性的历史比看起来便宜得多。

``````class SolutionState:
def __init__ (self, tuples=None, prev=None, delete_at=None, threshold=None):
if prev is None:
# Base object.
# Sort values by b increasing, then a decreasing.
self.tuples = sorted(tuples, key=lambda t: (t[1], -t[0]))
self.a = sum(t[0] for t in tuples)
self.b = sum(t[1] for t in tuples)
self.prev = None
self.delete_at = delete_at
self.deleted = 0
self.threshold = threshold
else:
# Links back to previous solutions.
self.tuples = prev.tuples # Cheap shallow copy!
t = self.tuples[delete_at]
self.a = prev.a - t[0]
self.b = prev.b - t[1]
self.prev = prev
self.delete_at = delete_at
self.deleted = prev.deleted + 1
if threshold is None:
self.threshold = prev.threshold
else:
self.threshold = threshold

def solution (self):
current = self
i = len(self.tuples)
while 0 < i:
i -= 1
if current.delete_at is None:
elif current.delete_at == i:
current = current.prev
else:

def score (self):
n = len(self.tuples) - self.deleted
if n == 0:
# Guarantee valid.
return self.threshold + 1
else:
return self.b / n

def is_valid (self):
return self.threshold < self.score()
``````

``a``

``b``

``score``
``is_valid``

``i``

``SolutionState``
。假设此时还有另一个
``SolutionState``

``a``
``b``

``a``

``i``
，对于每个删除次数
``d``
，我们都有一个最佳边缘。我们可以通过严格减少
``a``

``b``

``````by number of deletions d
list of SolutionStates, sorted by a descending, and b ascending
``````

``i``
``i+1``

``d``
，我们都有一个之前带有
``d``

``d-1``

``d``
，那么我们就可以就地更新这个数据结构。因为我们更新后就不再需要第
``d``

``````def find_optimal (threshold, tuples):
base = SolutionState(tuples=tuples)
base.threshold = threshold
if base.is_valid():
# Don't think too hard, deleting elements reduces a, so this is best.
return base.solution()
else:
optimal = [[base]]
best = None
for i in range(len(tuples)):
d = len(optimal)
optimal.append([]) # Add blank optimal fringe.
while 0 < d:
fringe_keep = optimal[d]
fringe_delete = [SolutionState(prev=ss, delete_at=i)
for ss in optimal[d-1]]

# Did we find possible final solutions?
while 0 < len(fringe_delete) and fringe_delete[-1].is_valid():
# Any further deletion reduces a
ss = fringe_delete.pop()
# Is this an improvement?
if best is None or best.a < ss.a:
best = ss

# Merge what's left
fringe_merge = []
j = 0
k = 0
while j < len(fringe_keep) and k < len(fringe_delete):
# Would fringe_delete[k] come after?
if fringe_keep[j].b <= fringe_delete[k].b:
# Is fringe_keep[j] in the fringe?
if fringe_delete[k].a < fringe_keep[j].a:
fringe_merge.append(fringe_keep[j])
j += 1
else:
# Check if fringe_delete[k] is kept.
if fringe_keep[j].a < fringe_delete[k].a:
fringe_merge.append(fringe_delete[k])
k += 1

# Keep remainder of whatever is left.
while j < len(fringe_keep):
fringe_merge.append(fringe_keep[j])
j += 1
while k < len(fringe_delete):
fringe_merge.append(fringe_delete[k])
k += 1

# Replace and move down.
optimal[d] = fringe_merge
d -= 1

# We might have empty fringes at top? Small optimization.
while 0 < len(optimal) and 0 == len(optimal[-1]):
optimal.pop()

# If nothing else, delete everything was valid.
return best.solution()
``````

``````tuples = [(10, 4), (7, 10), (3, 6), (1, 4), (1, 1)]
for threshold in range(11):
print(i, find_optimal(threshold, tuples))
``````

``n``

``a``

``A``
，那么这将使用最多空间和时间
``O(n*n*A)``