algorithm - 确定最佳资金分配的算法
问题描述
所以我有一个现实世界的情况，我正在努力寻找解决方案。为了简单起见，我将稍微抽象和调整细节。
我有一定数量的钱可以贡献给一个或多个桶。这些桶包含 0 个或更多其他人贡献的钱。有一定的红利，将在所有桶中平均分配，无论每个桶中有多少钱。我将获得的股息百分比是基于我在特定存储桶中的持有量相对于该存储桶中总持有量的百分比。
我怎样才能确定我的资金在不同的桶中的最佳分配，以最大限度地提高我的收益？
例如：
- 我有 100 美元可以投资。
- 总股息为 100 美元。
- 已经有 3 个存储桶包含以下资金。--- 桶 A：100 美元 --- 桶 B：200 美元 --- 桶 C：300 美元
因此，一种方法是我可以将全部 100 美元放入桶 A。我将拥有该桶 50% 的份额，因此将获得 16.66 美元的股息 ((100 / 3) * .5)。
我认为解决方案并不像找到我拥有最高百分比的单个存储桶那么简单。例如，如果桶如下：
--- 桶 A：33.33 美元 --- 桶 B：33.33 美元 --- 桶 C：33.33 美元
我最好将我的钱平均分配到所有 3 个桶中，并从每个桶中收取 16.66 美元。
无论如何，寻找一种算法来确定理想的分配。
不确定要尝试什么。我唯一能真正想到的就是通过为每个存储桶枚举 0-100 的所有可能组合来进行暴力破解，但这在性能方面很快就会变得很糟糕。
（FWIW，这不是家庭作业或编码挑战——我正在做的事情的真实生活场景）
解决方案
从概念上讲，您希望添加到最低的存储桶，直到它与第二低的匹配。添加到最低的 2，直到它们与第三个匹配。然后添加到最低的 3，依此类推。这意味着每一美元都用于最好的投资。
问题归结为弄清楚你将增加多少水平，然后你将投入多少。
让我们假设桶开始时buckets = [400, 800, 100, 200]你必须1100投资。
首先我们按数量排序buckets = sorted[buckets]得到[100, 200, 400, 800]。
接下来我们看看成对的差异。 [200-100, 400-200, 800-400] = [100, 200, 400]. 这代表我们必须增加多少桶。
现在，我们将每个成对差异乘以我们在该点填充的桶数，以获得达到这些阈值的美元价值。 [100*1, 200*2, 400*3] = [100, 400, 1200].
接下来，我们走水桶，弄清楚我们装了多少，用了多少钱。
start with 1100
bucket 1 cost us 100, 1000 left.
buckets 1,2 cost us 400, 600 left.
buckets 1,2,3 would cost us 1200 so we divide our remaining 600 3 ways for 200 in each.
向后进行计算，我们添加到200存储400桶、400存储200桶和存储桶。共花了。5001001100
现在你只需要编码它。:-)