arrays - 给定一个可以改变数字的符号，找到数组的最小和

Question

我在编码比赛中遇到了这个问题-

您将获得一个正整数数组，并且可以在需要时更改任何整数的符号。
编写一个程序来计算这个数组的最小和。这个总和应该 >= 0。
例如 :
当我们改变 1 和 5 {-1,2,4,-5} 的符号时，数组 = {1,2,4,5} 然后 sum = 0

我对这个问题的解决方案是对数组进行排序并找到所有成员的总和。然后我会从总和开始迭代地减少 2*(排序的数组值) - 从最大的数字开始 - 直到总和变为 0 或直到它变为负数。

但我的解决方案是错误的。取 12、13、14、15、16、50。我的代码会将 50 更改为 -50 并停止(即最小总和 = 20)。但答案应该是 12,-13,-14,-15,-16,50 (min sum = 4)

Answer 1

这个问题可以改成背包问题

考虑这个问题:

给你 n 个整数，很明显，你可以计算这些数字的总和，假设它是 S

您现在需要从中选择一组数字，并旨在将这些选择的数字相加尽可能接近 S/2

这可以使用与背包问题非常相似的 DP 算法来完成

你现在可以做吗？ :)

这篇文章只是一个提示，如果您需要更多帮助，我可以提供更多详细信息