与えられた:
- 特定のコンテナ タイプに配置するためのコストを持つアイテムのセット。
-それぞれが利用可能なコンテナの数を持つコンテナタイプのセット。
例：
量*容器タイプ: 5 * A、3 * B、2 * C
アイテム（費用）：
3 * X (A=2、B=3、C=1)
2 * Y (A=5、B=2、C=2)
1 * Z (A=3、B=3、C=1)
問題：
コストが最小限になるように、コンテナへのアイテムの最適な配置を見つけます。簡単にするために、アイテムは 1 つのタイプのコンテナにのみ配置します。
問題を解決するためにハンガリーの方法を試してみましたが、O(n³) のランタイムでは、大規模な問題 (たとえば、100000 アイテム) では非常に困難です。
私の現在の解決策は貪欲なアプローチです。つまり、アイテムとコンテナーの組み合わせをコスト (昇順) で並べ替え、O(n log n) に十分な量が残っている最初のコンテナーを割り当てるだけです。
より良い解決策はありますか？