CODEWITHSUNDEEP
javadynamicknapsack-problem
user2019594
user2019594

Reputation: 353

Recursive Knapsack returning wrong answer

The following code should be returning 16 as far as I can tell but for some reason, it returns 10. Does anyone know what my bug might be? Basically it's the Knapsack problem in Java and I've ran through the whole code on paper and it seems to return the right answer to me but I cannot figure out why when it's properly run, it returns back 10.

Any help would be much appreciated. Thanks!

import java.util.Stack;

public class knapsackProblem
{

  public static int optimalValue(Stack<item> items, int totalWeight)
  {
    if (items.isEmpty())
      return 0;

    int value = items.peek().value;
    int weight = items.peek().weight;

    items.pop();

    if (totalWeight<weight)
      return optimalValue(items, totalWeight);

    return Math.max(optimalValue(items,totalWeight), value + optimalValue(items, totalWeight-weight));
  }

  public static void main(String args[])
  {
    int knapsackWeight = 15;
    Stack<item> items = new Stack<item>();

    items.push(new item(7,10));
    items.push(new item(3,6));

    System.out.println(optimalValue(items, knapsackWeight));

  }
}

class item
{
  public int weight;
  public int value;

  public item(int aWeight, int aValue)
  {
    weight = aWeight;
    value = aValue;
  }
}

Upvotes: 1

Views: 126

Answers (2)

ajb
ajb

Reputation: 31689

I haven't gone through the whole algorithm, but an obvious problem is that every time you call optimalValue on a Stack, it will pop one or more items from the stack. But a Stack, and the items in the stack, are objects, which means they're passed around by reference. So in this line:

return Math.max(optimalValue(items,totalWeight), value + optimalValue(items, totalWeight-weight));

This calls optimalValue twice. The first time you call it with items as a parameter, optimalValue will pop one or more elements from items. Then the statement calls optimalValue again with items as a parameter--and this will NOT use the same items stack that you passed to the first optimalValue call, but it will use the items with the already-popped-off items still popped off (from the first call). I really doubt this is what you want. If you do things this way, then at some point I think you'll have to make a copy of your Stack. Or you'll need to rethink things and do it a different way (maybe you can use an array or ArrayList, so that the items aren't actually popped off but you could pass a "starting index" from one optimalValue call to the recursive call).

I don't know whether there are other problems with your solution in addition to this one.

Upvotes: 0

Tyler Lee
Tyler Lee

Reputation: 2785

Your Stack is being modified across the calls. So a line like 

return Math.max(optimalValue(items,totalWeight), value + optimalValue(items, totalWeight-weight));

will have two different copies of items for each call. Not what you want.

Instead of using Stack, try changing things around to use an ArrayList. Then pass your index of which item you're evaluating into the optimalValue method instead. This should help you work through the items correctly.

Upvotes: 1

Related Questions