时间戳

首页 > 解决方案 > 查找给定总和的最接近组合而无需替换

python - 查找给定总和的最接近组合而无需替换

问题描述

我一直在涉足编程，最初是在 VBA 中制作一个简单的宏，以在给定输入列表时找到某个组合，该组合总和为给定数字。我想象了一些任务和完成这些任务的分钟数，并输入了一些人来将他们之间的分钟数大致相等。举一个具体的例子，如果我有八个任务和三个人，我可能有以下变量：

M = [44,39,29,77,102,35,40,59]
N = 3
Avg = sum(M)/N

我希望程序能够为每个人找到最接近平均值的组合集。例如在这个例子中，我想要一个类似的输出：

A = [102, 40], B = [44,39,59], C = [29,77,35]

如果有人至少能在这个项目上引导我朝着正确的方向前进，我将不胜感激。虽然这开始于 Excel 工作表的宏之外，但如果我用更合适的语言（如 Python）了解更多关于优化算法的知识，我不介意。

标签： pythonvbacombinationsmathematical-optimizationcombinatorics

解决方案

让每个人的工作尽可能接近均值相当于最大最小公平分配问题

这本质上是一个优化问题——谷歌研究在这里做了一些工作

https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/45386.pdf

一位 CS 教授为此编写了一个 Python 模块https://github.com/anirudhSK/cell-codel/blob/master/schism/utils/max-min-fairness.py

推荐阅读