0

このプログラミングの質問は、難しい面接の最終ラウンドで受けました。

したがって、質問には同じサイズの 2 つのリストがあります。

List<Customer>, List<Products>

次のような関数があります

int score(Customer, Product)スコアを返します。

スコアが最大になる製品へのすべての顧客の割り当てを見つける必要があります。

それは NP 完全問題のようで、特に面接の数日後にまだ解決できなかった場合、面接で解決される可能性は低いです。今、私は解決策を知りたいだけです。
誰でも助けてもらえますか？

4

2 に答える 2

-1

これは、「スコアが最大になる製品へのすべての顧客の割り当てを見つけなければならない」に対する（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;
}
于 2013-10-10T22:40:57.477 に答える