提问人：Greedo 提问时间：8/25/2023 最后编辑：Greedo 更新时间：8/25/2023 访问量：44
按赃物份额在盗贼之间分配整根金条的算法
Algorithm for allocating whole gold bars amongst thieves by % share of the booty
问：
我有 N 根大金条和 1 根小金条，其重量相当于大金条的几分之一。例如，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）。如果几个分配同样接近（比如 4 个小偷之间平均分配 3 根金条，谁得到第 4 个金条），那么我不在乎算法选择哪一个。
答：
1赞
Matt Timmermans
8/25/2023
#1
适用于所选指标的简单算法是：
- 将每个人的目标份额四舍五入到整数个柱线，然后分配这些柱线。在 [0,1） 中，每个 theif 和一些剩余柱线都有一个残差目标。
- 如果您还剩下 M 根整根柱线，请将它们分配给剩余目标最高的盗贼，只要这些残差为 >= 0.5 根柱线。
- 将分数条给残差第二高的小偷，只要该残差>= 0.5x。
这将最大限度地减少平方误差，但可能会留下一些未分配的黄金。
如果您想施加必须分配所有黄金的额外限制，那么您可以这样做：
- 将每个人的目标份额四舍五入到整数个柱线，然后分配这些柱线。在 [0,1） 中，每个 theif 和一些剩余柱线都有一个残差目标。
- 如果您还剩下 M 整根金条，请将它们分配给剩余目标最高的盗贼。
- 将分数条给剩余数次高的小偷。
如果你想证明分配是最优的，不难证明将整个金条中的任何一个转移到其他盗贼都会产生更糟糕的分配。
评论
0赞
Greedo
8/29/2023
谢谢，第二种算法听起来像是一个很好的第一关。我正在考虑这样一种情况，即某人的残差恰好是“x”，但他们从 M 中分配了一个额外的整条，而不是完美大小的小条，因为其他残差更小。似乎有点次优，但我认为考虑到我的最小二乘法成本函数，那么你的算法在整个总体上是最优的
评论
(s1,s2,...sn)(r1,r2,...rn)