Dynamic Programming Subset Algorithm

Question

I am working on some review material for dynamic programming. I need to come up with how the subproblems should be divided, work out the base case, and come up with the recursive formula.

Given n positive integers a1,a2,...,an, a number k and a target W, we want to select a subset T with exactly k elements whose sum is closest to W. Each element can be chosen only once. Define a subproblem with 3 parameters (ie, C[x,y,z] = ...).

I have only worked with a few dynamic programming examples, and have never worked with one that needs 3 parameters in defining the subproblem. I am really lost here. If anyone can shine some light that would be great.

My best guess for what the subproblem should be is:

C[x,y,z] = x number of elements from {a1,...ay} where the sum is exactly z

But I have no idea if this is correct.

Andrew Tomazos Andrew Tomazos · Accepted Answer · 2012-06-27T01:35:17

One way to break this down into three parameters is:

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

Base case is C[0,0,0] = true, C[0,i > 0,j > 0] = false

Recursive case is:

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

This uses space O(n^2 * max(a_i)) (can be reduced to O(n*max(a_i)) by discarding C[i,,] as it is used)

Then just search C[n,i,j] for j near z for the final answer.

As a loop...

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];
}

As recursive function:

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]
}

Dynamic Programming Subset Algorithm

2 Answers