整数 A={1,3,60,24} と B={14,54,3} の 2 つのリストがあり、順序とリストの長さは未定です。Bの結果の分散ができるだけバランスがとれるように、Aの数値をBに入れるための最良の戦略は何ですか. 空きがない場合は、A のすべての数字を B に入れる必要はありません。ただし、空きがある場合は番号を入力する必要があります
Branch and Bound を適用しようと考えているのですが、どの枝を切るかを判断するために副問題 (完全に満たされていない) の分散を計算するなど、剪定条件を見つける方法がわかりません。
何か案は？
あなたが説明している問題は、パーティションの問題です( http://en.wikipedia.org/wiki/Partition_problem )。最適解を見つけることはNP完全ですが、ほとんどの場合にほぼ完璧な近似がいくつかあります。
実際、あなたが説明したアルゴリズムは、遊び場の子供たちがチームを選ぶ方法です。この貪欲なアルゴリズムは、セット内の数値が同程度の大きさである場合、非常にうまく機能します。確かに、これは最善の解決策ではありませんが、問題が NP 完全であることを考えると、その単純さの点で非常に優れています。
American Scientist のこの記事では、問題の優れた分析が提供されているため、一読して読む必要があります。問題）。
A と B の差から C[i]=A[i]-B[i] というリスト c を作成すると、それらの合計が 0 に近いすべての要素が見つかるはずです。この問題のようになります。しかし、この質問では負の数があり、それらの合計がゼロに近いサブセットを見つける必要があります。これは NP 完全問題だと思います。