は、それはお金

Question

の一定量を持つ人々に与えられたコストで、すべてのアイテムを販売することは可能です最近、私は、私は、以下のアルゴリズムのタスクとしてrefolmulateことができ、本当の問題に遭遇した：

問題：
を集合が与えられます多少の金額を持っているNの人物とM個のアイテムのセットは、それぞれ多少の費用がかかりますが、すべてのアイテムを売ることは可能ですか？

各アイテムは最大で1人で購入する必要があり、各人は複数のアイテムを購入することができ、そのコストは彼の持つ金額を超えないようにすることができます。

マイ未遂ソリューション：
私はネットワークを構築し、このような最大の流れを見つけるの方向に考えていた：
- 人に対応する部分に頂点を持つbipartideグラフを作成し、他の部分で - アイテムに。
- 人をソースSに接続し、人の金額にエッジ容量を設定します。
- アイテムをシンクTに接続し、エッジの容量をアイテムコストに設定します。
- 購入可能なアイテムに各人を接続し、アイテムのコストにエッジキャパシティを設定する

このネットワークで見つかった最大フローの各エッジが空であるか完全に飽和している場合、 Tに行くすべてのエッジが飽和している場合、誰がどのアイテムを購入すべきかを知りたければ、左と右のパートの間のエッジを見ます。

しかし、問題は、フローに部分的に塗りつぶされたエッジが含まれている可能性があることです（人が部分的に一部の商品を支払ったことを意味します）。この場合、私は排除できません。

Answer 1

明らかに、これはBin Packing Problemの種類です。

Multiple knapsack problemも参照してください。

Answer 2

複数のナップザックはこの問題を正確に解決しますが、すべての要素が同じ重量（ナップザックの視点からの価値）を持っているので、間違いなく過度です。

私の直感は、すべての反復で最も費用のかからない人に、まだ余裕がある貧しい人にすぐに売ろうとすると、貪欲なアルゴリズムを使用することを示唆しています。それは安価なものを売る前に商品を売ることができないなら、それをまったく販売しないという確信に基づいています。さらに、より貧しいバイヤーの予算を使い果たすことは、より高価なアイテムを購入するより多くの力を他人に残すことになります。私はそれを確認するのに十分なテストデータがあると思います。