假设我有 N 个物件，每个物件都有关联的值 A 和 B。这可以表示为元组串列，例如：

[(3,10), (8,4), (0,0), (20,7),...]

其中每个元组都是一个物件，两个值是 A 和 B。

我想要做的是从这些物件中选择 M 个（其中 M < N），以使所选子集中的 A 和 B 的总和尽可能平衡。这里的 M 是问题的一个自变量，我不想找到最优的 M。我希望能够说“给我 100 个物件，并让它们尽可能平衡”。

知道是否有一种有效的算法可以解决这个问题（不一定是完全最优的）？我认为这可能与装箱有关，但我不确定。

uj5u.com热心网友回复：

这是子集和的变体。将每个（A，B）替换为AB，然后所有选定的AB值之和的绝对值就是和的“不平衡度”。所以你真的必须从这些标量中选择 M 并尝试使总和尽可能接近 0。

“变体”位是因为您必须准确选择 M 个项目。（我认为这就是为什么你会想到装箱而不是子集和的原因。）如果你有一个黑盒子集和求解器，你也可以解释这一点：如果最大单对绝对差为 D，则替换每个 (A,B) 乘以 (A-B D) 并且目标总和为 M*D。（当然，如果您正在使用动态编程方法，请不要这样做，因为它会增加您正在使用的数字的大小。）

假设你对一个近似值很好（如果你不是，你会有一个真正糟糕的一天）我倾向于使用模拟退火或延迟接受爬山作为基本方法，从一个贪婪的初始解决方案开始（迭代地添加导致最小差异的任何物件），然后在每一轮中，考虑用一个当前未选择的物件随机替换一个物件。