0

DP を使用して問題の最適な解決策を得ることができました。私が直面している問題は、解決策を再構築したい場合、最適な解決策を得る方法が1つしかないことです。最適な結果につながる可能性のあるすべての方法/選択を後戻りできるような方法はありますか??

たとえば、スキル {1, 2, 2, 1} を持つプレーヤー a、b、c、d からチームを選択する場合、最適なチーム スキル数は 3 であり、これを達成するための 1 つの可能な方法を次のように得ることができます。 {{あいうえお}}。私が探しているのは、チームのスキル数を 3 として公平にチームを分割できるすべての方法、つまり {{a, c}, {b, d}} と {{a, b}、{c、d}}

4

2 に答える 2

0

X がプレイヤーの数の場合。(X-1)! 可能な解の数です。結果が最適なチーム スキルと等しい場合は、その結果を配列に格納します。

于 2013-08-09T17:31:12.963 に答える
0

DP の主なステップは、サブ問題の解決策を知ることによって問題の解決策を見つけることです。これは、副問題の最小 (または最大) 値を見つけることによって行われます。これにより、問題を最小 (または最大) 値を持つサブ問題に接続することで、有向グラフを作成できます。ページの最後の画像のように。すべての解決策を見つけるには、問題全体の解決策から可能なすべてのパスを見つけるだけです。

于 2013-08-10T08:45:31.050 に答える