動的プログラミングの問題に関するいくつかの指針を探しています。この種の問題を解決する方法に関する関連情報が見つかりません。動的計画法を使用して解決する方法を知っている唯一の問題は、2 つのシーケンスがあり、それらのシーケンスの行列を作成する場合です。しかし、それを次の問題に適用する方法がわかりません...
セット A = {7,11,33,71,111} と数値 B がある場合、A のサブセットである C には、合計 B を構築する A の要素が含まれます。
例：
A = {7,11,33,71,111}
If B = 18, then C = {7,11} (because 7+11 = 18)
If B = 3, then there is no solution
ここで助けてくれてありがとう、この種の問題を解決するときの考え方がわかりません。一般的な方法も見つかりません。遺伝子配列などに関するいくつかの例しかありません。
動的計画法はソリューションの広いカテゴリであり、中間結果を何度も再計算する代わりに、部分的なソリューションが次の反復のために何らかの構造に保持されます。
この特定の問題に対して動的なアプローチを取るとしたら、前のステップから計算可能なすべての合計と、その合計を計算するために使用されるセットの実行中のリストを保持することになるでしょう。
したがって、たとえば、作業セットに含まれる最初の反復に が含まれる場合、そのセット内のすべてのものとセット自体に{null, 7}追加します (ここではそのふりをしましょう)。これで、ワーキング セットには が含まれます。セット内の各値について、その結果をどのように取得したかを追跡します。したがって、元のセットにマップし、元のセットにマップします。反復は、A) ターゲット値が生成されるか、B) 値が見つからずに元のセットが使い果たされたときに終了します。順序付きセットを使用して負のケースを最適化できますが、それを理解することはあなたに任せます.11null+11=11{null, 7, 11, 18}7{7}18{7,11}
この問題にアプローチする方法は複数あります。2^(size of set)これは動的なソリューションであり、メンバーのセットを構築する必要があるため、あまり効率的ではありません。しかし、一般的なアプローチは、動的計画法が解決するために作成されたものに対応しています。