find items in knapsack bag

Question

I want to solve the knapsack problem recursively in C#. This is my code:

public  int f(int n, int remain)
{
    if (n < 0) return 0;
    if (w[n] > remain)
    {
        //    Thread.VolatileWrite(ref   check[n], 0);
        check[n] = 0;
        return f(n - 1, remain);
    }
    else
    {
        int a = f(n - 1, remain);
        int b = p[n] + f(n - 1, remain - w[n]);
        if (a >= b)
        {
            //   Thread.VolatileWrite(ref   check[n], 0);
            check[n] = 0;
            return a;
        }
        else
        {
            //  Thread.VolatileWrite(ref   check[n], 1);
            check[n] = 1;
            return b;
        }
    }
}

w is an array that holds weights and p is an array that holds prices. n is the number of items and remain is the maximum weight.

My problem is with the check array. I have used this array to store items that are going to be in the bag but it does not work always, sometimes the solution is right and sometimes not. I have tried everything but could not figure it out. How can I solve this?

Answer 1

The usage of the check array is wrong, since it indicates the last assignment, and it does not have to be the one chosen.

Here is a counter example that explains why it does not work.

Assume:

weights = [1,2]
values = [2,1]
w = 2

Now, let examine what will happen:

f(1,2):
   f(0,2):
       f(-1,2)  = 0
       a = 0
       f(-1,1) = 0
       b = 2 + 0 = 2
       b>a -> check[0] = 1
    return f(0,2) = 2
    a = 2
    f(0,0):
       w[0] > 0: check[0] = 0
       return f(-1,0) = 0
    return f(0,0) = 0
    b = 1 + 0 = 1
    a > b: check[1] = 0
return  f(1,2) = 2

So, the optimal solution to this problem is 2 (chosing the 2nd element), but your solution chose no element (check = [0,0])

This happens because the changing of check is global, and not local to the calling environment, and specifically - the assignment in deep levels do not depend on the choice you made in higher levels.

To handle it you can either:

1. make your list not global, and each recursive call will have its own instance of a list. The "parent" call will chose not only which value to take, but according to this choice - the parent will also chose the list it will use, and append "his" choice to it, before forwarding up to its parent.
2. Switch to a DP solution, or mimic the DP solution, and then use the table you created to figure out which elements to chose as I described in this thread: How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?