给定n个整数，找到它们的和的绝对值最小的m个数。

Question

4

我有给定的n个整数，包括正数和负数。如何找到一个好的算法，从这个列表中找出m个整数，使得这m个整数的绝对值之和最小？

- Neal

6

我认为“教授”希望你来决定……这是作业吗？ - pavium

2

这个问题并不愚蠢。它询问的是总和的绝对值，而不是绝对值的总和。对于{-10,1,2,3,10}和m=2，答案将是{-10,10}。 - Lior Kogan

@Lior Kogan - 哈哈，你明白我的问题了。 - Neal

1

@Neal - 新用户，提供了非常具体的单词问题，没有提供代码。如果不是作业，那么这是一个很好的巧合。您是否尝试过http://programmers.stackexchange.com？ - Jared Farrish

@Jared：从“你试过程序员.SE吗？”这句话来看，似乎你是这个意思。 - jscs

显示剩余6条评论

2个回答

2

如果“好”意味着“正确”，那么就尝试每一种可能性，这将花费你约 n 选择 m 的时间。非常缓慢。不幸的是，这通常是你在一般情况下所能做到的最好的，因为对于任何一组整数，你总可以添加一个更多的整数，它是另外 m-1 个整数的负数之和——并且这些其他整数都可以具有相同的符号，所以你无法搜索。

如果“好”意味着“快速且通常正常工作”，则有各种方法可供选择，例如：

假设你可以解决 m=2 的问题，并进一步假设你可以同时解决正负两个答案（然后取其中较小的一个）。现在假设你想解决 m=4。先解决 m=2，然后排除这两个数字并再次求解...接下来该怎么做显而易见！现在，m=6 呢？

现在假设你可以解决 m=3 和 m=2 的问题。你认为你可以得到 m=5 的一个不错的答案吗？

最后请注意，如果你将数字排序，你可以一次通过解决 m=2 来解决问题，并且对于 m=3，你需要进行一个令人讨厌的二次搜索，但至少你可以只对大约四分之一的列表进行两次操作（正数和负数的小一半）并寻找相反符号的数字来抵消。

- Rex Kerr

kerr - “正确”的想法很容易得到，但我试图让它“快速且通常运行良好”，然后发现并不那么容易，因为正如你所说，m 可能会改变... - Neal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trutheality · Accepted Answer

这个问题是NP难问题，因为有效地解决它将会有效地解决子集和问题。

考虑到这一点，除非你相信P=NP，否则你不可能找到一个有效的算法来解决它。

你总是可以想出一些启发式方法来指导你的搜索，但在最坏的情况下，你将不得不检查每个包含m个整数的子集。