algorithm - 找到客户对产品的最佳评分分配

Question

我在最后一轮艰难的面试中得到了这个编程问题。

所以这个问题有两个相同大小的列表。

List<Customer>, List<Products>

有一个功能如下

int score(Customer, Product)并返回一个分数。

我必须找到将所有客户分配给分数应该最高的产品。

这似乎是一个 NP 完全问题，我不太可能在面试中解决，尤其是在面试后几天我仍然无法解决的情况下。现在我只是想知道解决方案。
有人可以帮忙吗？

Answer 1

您可以将其建模为要找到最大匹配的加权二分图。

关于匹配的维基百科有这个可能有用的答案：

在加权二分图中，每条边都有一个关联值。最大加权二分匹配被定义为匹配中边的值之和具有最大值的匹配。如果图不是完全二分图，则以零值插入缺失的边。找到这样的匹配被称为分配问题。它可以通过在增广路径算法中使用修改后的最短路径搜索来解决。如果使用 Bellman-Ford 算法，运行时间变为 O(V^2 E)，或者边缘成本可以移动，有可能使用 Dijkstra 实现 O(V^2 log(V) + VE) 运行时间算法和斐波那契堆。卓越的匈牙利算法解决了分配问题，它是组合优化算法的开端之一。

Answer 2

这是一个（Java）解决方案，“我必须找到将所有客户分配给分数应该最高的产品”。

对于 C 客户和 P 产品，它在 O(CP) 时间内运行。

请注意，由于未提供 score() 函数的定义，因此我没有测试此代码。

Map<Customer, Product> solve(List<Customer> customers, List<Product> products)
{
    Map<Customer, Product> result = new HashMap<Customer, Product>();

    for (Customer customer : customers)
    {
        int maxScore = Integer.MIN_VALUE;
        Product bestProduct = null;

        for (Product product : products)
        {
            int currentScore = score(customer, product);

            if (currentScore > maxScore)
            {
                maxScore = currentScore;
                bestProduct = product;
            }
        }

        if (bestProduct != null)
        {
            result.put(customer, product);
        }
    }

    return result;
}