2

私は、動的計画法のいくつかのレビュー資料に取り組んでいます。部分問題をどのように分割するかを考え出し、基本ケースを考え出し、再帰式を考え出す必要があります。

n 個の正の整数 a1,a2,...,an、数値 k、およびターゲット W が与えられた場合、合計が W に最も近い要素が正確に k 個あるサブセット T を選択します。各要素は 1 回だけ選択できます。3 つのパラメーター (つまり、C[x,y,z] = ...) を持つ部分問題を定義します。

私はいくつかの動的プログラミングの例しか扱ったことがなく、部分問題の定義に 3 つのパラメーターを必要とするものは扱ったことはありません。私はここで本当に迷っています。誰かが光を当てることができれば、それは素晴らしいことです。

サブ問題がどうあるべきかについての私の最善の推測は次のとおりです。

C[x,y,z] = {a1,...ay} からの x 個の要素で、合計は正確に z です

しかし、これが正しいかどうかはわかりません。

4

2 に答える 2

2

これを 3 つのパラメーターに分解する 1 つの方法は、次のとおりです。

x: maximum index of item considered for inclusion in subset
n: number of items in subset
s: sum of subset

基本ケースは C[0,0,0] = true、C[​​0,i > 0,j > 0] = false

再帰的なケースは次のとおりです。

C[i,n+1,s+a_i] = C[i-1,n,s]  // use item i
C[i,n,s] = C[i-1,n,s] // dont use item i

これはスペース O(n^2 * max(a_i)) を使用します (使用されている C[i, , ] を破棄することで O(n*max(a_i)) に減らすことができます)

次に、C[n、i、j]でzの近くのjを検索して、最終的な答えを求めます。

ループとして…

for (int i = 1; i <= n; i++)
{
    C[i,n+1,s+a_i] ||= C[i-1,n,s];
    C[i,n,s] ||= C[i-1,n,s];
}

再帰関数として:

bool C(int maxindex, int size, int sum)
{
    if (memoize(maxindex, size, sum))
         return cached;

    if (maxindex == 0)
        return (size == 0 && sum == 0);

    return
         C(maxindex-1, size-1, sum - A[maxindex]) ||  // version using A[maxindex]
         C(maxindex-1, size, sum); // version not using A[maxindex]
}
于 2012-06-27T01:35:17.830 に答える
0

この場合、C(x,y,z) を、{a1 ... ax} から正確に y を使用して正確に z の合計を得ることができるかどうかを表すブール値にします。

まったく同じ問題ではありませんが、Wikipediaには、説明付きのさまざまな同様の問題に対する動的プログラミングソリューションがあります。ひょっとしたら、これはあなたにいくつかのアイデアを与えるかもしれません。

于 2012-06-27T01:28:32.943 に答える