部分和問題 個の正整数 がある。この中からいくつかを選び、その和をちょうど にする ことが出来るかどうかを判定する問題を部分和問題と言う。 :; を次のように定義する この問題を解くために、 :; このとき 。 の中からいくつかを選び その和をちょうど にすることができる時 それ以外の時 :; の値は、次の漸化式を用いて計算できる。 :; :; ある時点で :; を選ばない または を選ぶ の場合 それ以外の場合 :; を選ばない または かつ : ; を選ぶ の場合 それ以外の場合 となれば、部分和問題の答えは「L 」であり、 分和問題の答えは「」である。 :; は、 :; であれば、部 の部分集合でその和が となるような部分集合全体を表す状態である と考えることが出来る。この問題の場合、そのような部分集合が存在するかどうかだけを知れば良 いので、 : ; の値として または を用いれば良い。このように、多くの部分集合を :; という データに集約することで、列挙の数を減らし、計算効率を高めている。このような考え方を動的計 % )$$ と言う。 画法 すなおに実装すると、 : ; の値を格納するのに、２次元配列を用いることになるが、 : ; の値 :# ; # の値から計算できるので、一次元配列を使いまわして、配列の後ろの要 素から前の要素へと計算を進めていくことができる。 は、 アルゴリズムの概略 を整数型の変数 "# 整数型の配列 ?@ . +5 + "/# 整数型の変数 に読み込む。 $ 整数型の配列 に対して、?@ 5 # ?@ 5 . +5 +5 / と初期化する。（空集合 で部分和 を実現できる。） % +5 + " なる各 に対して順に を一つずつ増やしながら ./ ,5 ,5 ?@ なる各 に対して順に を一つずつ減らしながら ? ?@@ が なら ?@ 5 とする（ を選ぶ場合に相当する） ? @ が になれば「L 」と出力して終了 & ここが実行されるということは :; であることを意味するので、「」と出力して 終了 演習 %& 部分和問題を解くプログラムを作成して、データファイル 4∼4 に記載さ れている部分和問題の解を求めよ。なお、データファイルの１行目には 行目には 個の整数 の値が書かれており、２ が間に空白を含む形で書かれており３行目には の値が書か れている。
© Copyright 2024 ExpyDoc
