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 · Accepted Answer · 2012-06-27 01:52:53Z

2

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

edited Jun 27, 2012 at 1:52

answered Jun 27, 2012 at 1:35

Andrew Tomazos

69.3k46 gold badges208 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Tesla Over a year ago

Hmm, how would just the recursive function look for this? I am used to developing a recursive function, and moving on to the pseudocode from there. Is that possible to derive from this? Some along the lines of C[x,y,z] = { ... }

Andrew Tomazos Over a year ago

@Telsa: added loop and recursive function

Antimony · Accepted Answer · 2012-06-27 01:34:20Z

0

In this case, I'd let C(x,y,z) be a boolean representing whether it is possible to have a sum of exactly z using exactly y from {a1 ... ax}.

Although it isn't the exact same problem Wikipedia, has dynamic programming solutions for a variety of similar problems with explanations. Perhaps this might give you some ideas.

edited Jun 27, 2012 at 1:34

answered Jun 27, 2012 at 1:28

Antimony

39.8k13 gold badges103 silver badges115 bronze badges

Collectives™ on Stack Overflow

Dynamic Programming Subset Algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related