按照战利品百分比在小偷之间分配整条金条的算法

Question

我有 N 根大金条和 1 根小金条，其重量相当于一根大金条的 x 的一部分。例如，N = 10 且 x = 0.5，那么我有 10.5 块大金条，其中 10 块大金条和 1 块小金条

我想在一群 T 盗贼之间分配这个，其中盗贼 i (T_i) 拥有他或她应该有权获得的一份 (s_i) 黄金。例如。对于 T = 3，则小偷 1 拥有 40% 份额，小偷 2 拥有 50% 份额，小偷 3 拥有 10% 份额

我可以运行什么算法将金条分配给小偷，以便总黄金的最终份额（按重量）最接近他们想要的份额？金条不能被切割或分割，它们必须保持完整。

---

我的想法示例，每个小偷都会获得 NearestInteger((Tot Gold) * s_i) 金币，其中 Tot Gold = N + x = 10.5

使用上面的数字执行此方法

小偷	分享s_i	10.5 *分享	圆形
1	40%	4.2	4
2	50%	5.25	5
3	10%	1.05	1

有几个问题

• 总分配是 4+5+1 = 10 而不是 10.5，因为每个人的黄金都是向下取整的。但如果每个人都碰巧被四舍五入，它也可能最终会过度。
• 该算法永远不会分配小部分金条，因为它以整数形式工作。
• 我不知道这是否是最接近的最终比例

一种扩展是将剩余的黄金分配给小偷 N（最后一个人），但这会使他们倾向于总是获得剩余的黄金。

---

更新：测量最佳

定义什么是“最好”；我认为一种措施是找到一种算法，该算法可以最小化所需份额（s1，s2，...sn）与运行算法后的结果份额（r1，r2，...rn）之间的毕达哥拉斯距离。如果几个分配同样接近（比如 3 个小偷平均分配 4 个金条，谁得到第 4 个），那么我不在乎算法选择哪一个。

Answer 1

适用于您选择的指标的简单算法是：

• 将每个人的目标份额四舍五入为整数条，然后分配这些条。对于每个 theif 和一些剩余的条形，您将在 [0,1) 中留下一个剩余目标。
• 如果剩余 M 个整条，将它们分配给残差目标最高的小偷，只要这些残差 >= 0.5 个条即可。
• 将分数条交给具有下一个最高残差的小偷，只要该残差 >= 0.5x。

这将最大限度地减少平方误差，但可能会留下一些未分配的黄金。

如果您想施加额外的限制，即所有黄金都必须分配，那么您可以这样做：

• 将每个人的目标份额四舍五入为整数条，然后分配这些条。对于每个 theif 和一些剩余的条形，您将在 [0,1) 中留下一个剩余目标。
• 如果你还剩下 M 个完整的金条，请将它们分配给剩余目标最高的盗贼。
• 将分数条交给剩余第二高的小偷。

如果你想证明分配是最优的，那么不难证明将任何整个金条移给其他小偷都会产生更糟糕的分配。