Recursive Knapsack Java -- Errors

Question

yet another knapsack question... I understand the concept of the knapsack problem but I am having troubles with parts of my code.. I would like to believe that I am headed into the right direction but maybe not?

Let's say I have a list of 1,2,3,6,7 and my goal weight is 4:
The items that will equal this weight are 1 and 3. 
My first iteration will go like this:
Item: 1
Goal Weight: 3 (I did weight - the item)
Items: 1,2
Goal Weight: 1
Items: 1,2,3
Goal Weight: -2
-- Once the weight reaches < 0, it should restart the goal weight and then restart the position    
but the items should start at 1 and skip over 2, going straight to 3. An Example below:
Items: 1
Goal Weight: 3
Items: 1, 3
Goal Weight: 0 // Finished

--However, I do not know how skip over the 2 and go to 3. In a way, I understand that this problem uses combinations/permutations. I just can't get my code to work the way I want it to. Below is my code. Please let me know if I am unclear in anything.

    public boolean recursive(int weight, int start){
       if(weight == 0){// if weight is zero, we found what we wanted.
           System.out.println("We did it");
           return true;
       }
       else if(weight < 0){ //Too much weight in the bag.
           if(start == storeItems.length-1){ //reached the end of the array.
           recursive(goalWeight, start + 1);
           return false;
           }
           else{ // did not reach end of the array but still not the right combination of numbers.
              recursive(weight, start + 1);
           }
       }
       else if(weight > 0){
           System.out.println(storeItems[start]);
           boolean x = recursive(weight - storeItems[start], start + 1);
       }else{
           System.out.print("No values");
       }
    return false;

}

Possible duplicate of http://stackoverflow.com/questions/19285021/recursive-knapsack-java?rq=1 and/or http://stackoverflow.com/questions/7774769/how-do-i-solve-the-classic-knapsack-algorithm-recursively?rq=1 — PM 77-1, Nov 04 '13 at 19:32

score 0 · Accepted Answer · answered Nov 05 '13 at 18:20

So, I figured out the answer to my question: How can I get a combination of each element in my array

My code demonstrates the use of a boolean. With this boolean labeled 'x', it will traverse the rest of my recursion, looking for the correct combination until x should return false. Without giving away the answer to people who were potentially stuck where I was, I will give a small code example.

boolean x = recursive(weight - storeItems[start], start + 1)

Using this piece of code, one can restructure the above base cases to determine whether the above piece of code will return true or false. If it returns true, then it should print out all of the necessary data that added up to the goal weight. If it returns false, then it should continue to the next item in the list.

Things to keep in mind: Calling this boolean does not mean you will alter any variables in "our world", what the boolean does is it goes into it's own recursive dive without actually altering anything we originally had. This is where the thought of "unwinding" a recursive dive comes in, because once the boolean finds its answer, it will unwind the recursive dive, allowing the boolean to check the combinations without ever changing your start position unless necessary.

Recursive Knapsack Java -- Errors

1 Answers1

Linked