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?

Please include a specific input for which the actual result differs from the desired result. What is the return value of `f`? The weight of a found solution? — Codor, Apr 19 '15 at 18:27
The return value should be right. Take care of modifying the check array inside the recursion. Try to copy the array every time, and return it in a tuple. It is not optimal, but you can see it better — rpax, Apr 19 '15 at 19:16
@codor w is an array that consists of wights and p is an array consists of prices...n is the number of items and remain is maximum wight — ali najimi, Apr 19 '15 at 19:28
@rpax yeah the return value is right....i don not get what u r suggesting could u give me an example? — ali najimi, Apr 19 '15 at 19:30

score 2 · Answer 1 · edited May 23 '17 at 11:43

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:

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.
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]?

Good answer. I love the answers to homework questions that are not _here is the code_ answers, teaching how to think and solve the problem. Thanks for making this site better. — rpax, Apr 20 '15 at 05:33
@amit sorry to ask for the code......but a little more hint wont hurt about the first solution u suggested — ali najimi, Apr 20 '15 at 14:41

find items in knapsack bag

1 Answers1

Linked