1

これが NP 困難な問題であることは承知していますが、多くのユーザーがこの機能を要求してきました (基本的に、現在の注文のアイテムのセットは、私たちが実行している取引の 1 つに適格ですか? または、現在のご注文の商品と他の 1 つの商品が対象となりますか?)

機能を提供することは、正しい答えを見つけることよりもユーザーの利便性に関するものであるため、X 個以上の項目がある場合はアルゴリズムを実行しないなど、時間をかけずにこれを行うためのショートカットを検討してきました。ラグ、またはアルゴリズムを介して最近追加された X アイテムのみを実行します。

アドバイスを提供できる前に、同様の問題に対処した人はいますか?

4

1 に答える 1

2

pidgeonholeを考えてください。この方法は、すべての場合でO（m + n）の複雑さです。

各「取引」を一連のルールに結合し、アイテムをループして、ルールが満たされる各pidgeonholeに追加します。

次に、取引をループし、アイテムがピジョンホールにある場合はピジョンホールからアイテムを引き出します。

例：

"blue car", "red car", "yellow expensive car", "red expensive car", "cheap car"

お得な情報：

buy a red car, get a blue car for free
buy an expensive car, get a cheap car for free

推測できる「ルール」：

is_red, is_expensive, is_blue, is_cheap

したがって、is_redとis_expensiveの2つの穴があります。アイテムをループして、ルールが満たされているすべての穴に追加し、次の穴を作成します。

is_red ( "red car", "red expensive car" )
is_expensive ( "red expensive car", yellow expensive car" )
is_blue ( "blue car" )
is_cheap ( "cheap car" )

次に、取引をループします。

buy a red car, get a blue car for free
is_red contains "red car", is_blue contains "blue car", so:
    pop them from the holes and make them a deal

次の取引：

buy an expensive car, get a cheap car for free
is_expensive doesn't contain any cars
于 2012-03-12T05:03:09.837 に答える