ここの例と非常によく似た問題を解決しようとしています: https://pythonhosted.org/PuLP/CaseStudies/a_set_partitioning_problem.html
これは、PuLP と呼ばれる最適化フレームワークを使用して、結婚式でゲストに座席を割り当てます。
いくつかのコンテキストを提供するために、各テーブルに N 人のゲスト、T テーブル、最大 S 席があります。各ゲストが他のゲストとどのくらい座りたいかを表すコスト マトリックス (N x N) があります。
最初のコード セクションでは、可能なすべてのテーブルのリストを作成しています。
possible_tables = [tuple(c) for c in pulp.allcombinations(guests,
max_table_size)]
これは私には意味がありません。候補テーブルの生成がアルゴリズムの外部で行われるとは思っていませんでした。
これは、単にN choose K候補を生成し、コスト マトリックスを使用して生成されたテーブルをスコア付けし、最適なテーブルを選択することとは大きく異なりますか?
私は PuLP の使用に限定されません。私はcvxpy、jump、mini-zincなどを見てきました。選択されたセットの要素間にそのような相互作用がある場合、目的と制約を定式化する方法に問題があります(ナップサック問題のアイテムが嫌われているかのようです)またはお互いを愛していた!)