algorithm - 分区浮点数组

Question

在写代码的时候，我发现了如下问题，简单来说一下：

对数组A和B中的浮点数组X进行分区，以使A中的值之和与B的值之和之间的差异最小化

这是我正在进行的调查的一部分，但我找不到有效执行此操作的方法。

编辑：

要回答那些认为这是来自 PE、SPOJ 或家庭作业等数学竞赛的人，事实并非如此。当我试图在因子a和b 的集合中划分一个已经分解的数字p使得 b = a + 1时，我只是对此感到好奇。如果我们从双方获取日志，我们可以证明这个问题等同于最小化总和的差异，但这就是我遇到的问题。

Answer 1

只是第一个简单的想法。使用动态规划方法。
我假设这个问题可以转化为背包问题。您需要从中选择项目X（将有 array A）以最大化总和但不超过(sumX - sumA)值（将有来自 array 的项目总和B）。对于通过动态编程方法解决背包问题的算法，请查看wiki ，例如
这个解决方案可能是错误的，顺便说一句......但即使它会起作用，我也非常确定存在更高效、优雅和简短的解决方案。