Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

My alghoritm works and produces good result, but it takes too much time(6 s for 300 input items that is too much for branch and bound alghoritm), so I have maken a mistake somewhere, but really can't find it :( It is supposed to be depth-first branch and bound. Any help would be appreciated!

public void knapsack2(Item[] items, int maxWeight)
{
    Item firstNode, secondNode, tempNode;

    int weight, bestValue = 0, bestWeight = 0;

    Stack stack = new Stack();

    firstNode = items[0];

    firstNode.setBound(bound(firstNode, maxWeight, items));

    stack.push(firstNode);

    Item bestNode = firstNode;

    while(!stack.isEmpty())
    {
        tempNode = (Item) stack.pop();
        weight = tempNode.getWeight();


        if( tempNode.getBound() > bestValue)
        {
            firstNode = new Item();
            firstNode.setLevel(tempNode.getLevel() + 1);
            firstNode.setValue(tempNode, items[firstNode.getLevel()].getValue());
            firstNode.setWeight(weight + items[firstNode.getLevel()].getWeight());
            firstNode.setBound(bound(firstNode, maxWeight, items));

            if(firstNode.getValue() > bestValue && firstNode.getWeight() <= maxWeight)
            {
                bestValue = firstNode.getValue();
                bestWeight = firstNode.getWeight();

                bestNode = firstNode;

            }

            if(firstNode.getBound() > bestValue)
            {
                stack.push(firstNode);
            }

            secondNode = new Item();
            secondNode.setLevel(tempNode.getLevel() + 1);
            secondNode.setValue(tempNode, 0);
            secondNode.setWeight(weight);
            secondNode.setBound(bound(secondNode, maxWeight, items));

            if(secondNode.getBound() > bestValue)
            {
                stack.push(secondNode);
            }
        }
    }

    System.out.println("Best value " + bestValue);
}

Bound function:

    public float bound(Item item, int maxWeight, Item[] items)
    {
    int j, k;
    int totalWeight;
    float result;

    if(item.getWeight() > maxWeight)
    {
        return 0;
    }
    else
    {
        result = item.getValue();
        j = item.getLevel() + 1;
        totalWeight = item.getWeight();

        while(j < items.length && (totalWeight + items[j].getWeight() <= maxWeight))
        {
            totalWeight += items[j].getWeight();
            result += items[j].getValue();
            j++;
        }
    }

    k = j;

    if(k < items.length)
    {
        result = result + (maxWeight - totalWeight) * (items[k].getValue() / (float) items[k].getWeight());
        return result;
    }

    return 0;
}
share|improve this question
1  
Out of curiosity -- what does that node object look like? – Joseph Weissman Nov 21 '12 at 15:32
Just setters and getters, does nothing actually. – Olga Nov 21 '12 at 17:19
Could you post a complete example (300 objects) - it could be just a memory allocation problem because b&b needs a lot of objects. – cat_baxter Nov 21 '12 at 22:14
1  
profile it and debug it. either with a profiler and debugger, or with print and System.currentTimeMillis() statements. – tb- Nov 23 '12 at 18:45

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.