数据帧中的置换值

Question

我有一个数据框，索引中有人名，列中有水果名，值是人到水果的距离。像这样

(index)   apple  orange  lemon  grape
John      22.3   13.1    14.9   8.8
Mike      12.1   14.2    11.3   5.3
Kevin     9.13   14.9    3.3    22.3
Leon      11.9   13.2    7.14   21.1
Joe       1.15   23.12   11.11  3.18
Frank     4.13   4.13    3.12   29.3
Ralph     7.8    23.1    14.4   29.0

一个人只能摘一个水果，我需要找到整体最低距离（因此我需要将所有组合的总距离相加，并找到最低距离）和摘每个水果的人的姓名

解决这个问题的最好方法是使用itertools.permutation

Answer 1

假设您需要每个水果由不同的人采摘，您可以使用itertools来评估名称和水果的所有可能组合，但这对于更大的问题来说是难以解决的

典型的解决方案是使用Integer Programming。Python有许多库可以帮助您解决IP问题。例如，下面是使用CVXPY库解决问题的方法：

import numpy as np
import pandas as pd
import cvxpy as cp
from io import StringIO

data = """name   apple  orange  lemon  grape
John      22.3   13.1    14.9   8.8
Mike      12.1   14.2    11.3   5.3
Kevin     9.13   14.9    3.3    22.3
Leon      11.9   13.2    7.14   21.1
Joe       1.15   23.12   11.11  3.18
Frank     4.13   4.13    3.12   29.3
Ralph     7.8    23.1    14.4   29.0"""
df = pd.read_csv(StringIO(data), sep="\s+", index_col=0)

# Define the decision variable as a matrix of boolean values with 
# len(names) rows and len(fruits) columns
x = cp.Variable(shape=(len(df.index), len(df.columns)), boolean=True)

# Define the objective function as the sum distances
objective = cp.sum(cp.multiply(df.values, x))

# Constrain the problem so that each person picks a single fruit 
# and each fruit is picked by someone
constraint1 = cp.sum(x, axis=0) == 1
constraint2 = cp.sum(x, axis=1) <= 1

# Define the problem and fins solution
problem = cp.Problem(cp.Minimize(objective), [constraint1, constraint2])
problem.solve()

结果是：

>>> x.value.round()
array([[0., 0., 0., 0.],
       [0., 0., 0., 1.],
       [0., 0., 1., 0.],
       [0., 0., 0., 0.],
       [1., 0., 0., 0.],
       [0., 1., 0., 0.],
       [0., 0., 0., 0.]])

意思是乔摘苹果，弗兰克摘橘子，凯文摘柠檬，迈克摘葡萄