7

我有一个数字列表（例如：）[-1, 1, -4, 5]，我必须从列表中删除数字而不更改列表的总和。我想删除可能具有最大绝对值的数字，而不改变总数，在示例中删除[-1, -4, 5]将离开[1]，因此总和不会改变。

我写了一种简单的方法，即找出所有不改变总数的可能组合，看看哪个组合消除了最大的绝对值。但这真的很慢，因为实际列表会比这大得多。

这是我的组合代码：

from itertools import chain, combinations

def remove(items):
    all_comb = chain.from_iterable(combinations(items, n+1) 
                                   for n in xrange(len(items)))
    biggest = None
    biggest_sum = 0
    for comb in all_comb:
        if sum(comb) != 0:
            continue # this comb would change total, skip
        abs_sum = sum(abs(item) for item in comb)
        if abs_sum > biggest_sum:
            biggest = comb
            biggest_sum = abs_sum
    return biggest

print remove([-1, 1, -4, 5])

它可以正确打印(-1, -4, 5)。但是，我正在寻找一些比遍历所有可能的项目组合更聪明、更有效的解决方案。

有任何想法吗？

4

5 回答 5

11

如果您将问题重新定义为找到总和等于完整集值的子集，您将意识到这是一个 NP-Hard 问题，（子集总和）

所以这个问题没有多项式复杂度解决方案。

于 2009-12-19T11:36:01.027 回答
4 
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Copyright © 2009 Clóvis Fabrício Costa
# Licensed under GPL version 3.0 or higher

def posneg_calcsums(subset):
    sums = {}
    for group in chain.from_iterable(combinations(subset, n+1) 
                                     for n in xrange(len(subset))):
        sums[sum(group)] = group
    return sums

def posneg(items):
    positive = posneg_calcsums([item for item in items if item > 0])
    negative = posneg_calcsums([item for item in items if item < 0])
    for n in sorted(positive, reverse=True):
        if -n in negative:
            return positive[n] + negative[-n]
    else:
        return None

print posneg([-1, 1, -4, 5])
print posneg([6, 44, 1, -7, -6, 19])

它工作正常，并且比我的第一种方法快得多。感谢 Alon 的 wikipedia 链接和 #python irc 频道上的 ivazquez|laptop 提供了一个很好的提示，使我找到了解决方案。

我认为它可以进一步优化——一旦找到解决方案，我想要一种方法来停止计算昂贵的部分。我会继续努力。

于 2009-12-19T18:46:15.627 回答
0

我不使用 Python 编程，所以我很抱歉没有提供代码。但我想我可以帮助算法：

  1. 求总和
  2. 将具有最低值的数字相加，直到得到相同的总和
  3. 其他都可以删

我希望这有帮助

于 2009-12-19T12:06:42.500 回答
0

您的要求并未说明该功能是否允许更改列表顺序。这是一种可能性：

def remove(items):
    items.sort()
    running = original = sum(items)
    try:
        items.index(original) # we just want the exception
        return [original]
    except ValueError:
        pass
    if abs(items[0]) > items[-1]:
        running -= items.pop(0)
    else:
        running -= items.pop()
    while running != original:
        try:
            running -= items.pop(items.index(original - running))
        except ValueError:
            if running > original:
                running -= items.pop()
            elif running < original:
                running -= items.pop(0)
    return items

这对列表进行排序（大项目将在末尾，较小的项目将在开头）并计算总和，并从列表中删除一个项目。然后它继续删除项目，直到新总数等于原始总数。保留顺序的替代版本可以编写为包装器：

from copy import copy

def remove_preserve_order(items):
    a = remove(copy(items))
    return [x for x in items if x in a]

collections.deque虽然如果你真的想保持秩序，你可能应该重写它。如果您可以保证列表中的唯一性，则可以通过使用 aset来获得巨大的胜利。

我们可能会编写一个更好的版本来遍历列表以找到每次最接近运行总数的两个数字并删除两者中更接近的一个，但是我们最终可能会得到 O(N^2) 的性能。我相信这段代码的性能将是 O(N*log(N))，因为它只需要对列表进行排序（我希望 Python 的列表排序不是 O(N^2)）然后得到总和。

于 2009-12-19T12:20:14.163 回答
0

这可以使用整数规划来解决。您可以为每个列表元素 x_i 定义一个二进制变量 s_i 并最小化 \sum_i s_i，受限于 \sum_i (x_i*s_i) 等于列表的原始总和的约束。

这是使用lpSolveR 中的包的实现：

library(lpSolve)
get.subset <- function(lst) {
  res <- lp("min", rep(1, length(lst)), matrix(lst, nrow=1), "=", sum(lst),
            binary.vec=seq_along(lst))
  lst[res$solution > 0.999]
}

现在，我们可以用几个例子来测试它：

get.subset(c(1, -1, -4, 5))
# [1] 1
get.subset(c(6, 44, 1, -7, -6, 19))
# [1] 44 -6 19
get.subset(c(1, 2, 3, 4))
# [1] 1 2 3 4
于 2014-05-07T18:03:37.173 回答