假设我有这个:
1A=6 2A=4.5 3A=6
1B=7 2B=6 3B=7.5
1C=6 2C=6.75 3C=9
我想找到产生最高总和的数字组合。字母前的数字不能多次使用,数字后的字母也不能多次使用。例如。 1A+2B+3C, 1C+2B+3A
有效。 1A+1B+2B,3A+2B+3B,1A+2A+3A
无效。
在这种情况下,最高总和是 1A+2B+3C=21
。我如何使用 python 找到这个结果和组合?
提前致谢
最佳答案
对于每个具有相同数字前缀的条目,找出其中的最大值。然后将所有这些最大值相加,您将得到给定限制条件下的最大值。
如果数字和字母必须是唯一的,那么这就成了一个可以用Hungarian algorithm 解决的问题。 .
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time
[...]
来自assignment problem的描述:
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph.
In its most general form, the problem is as follows:
There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.
关于python - 找出数字组合中的最高总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16411326/