# What is wrong with my knapsack alghoritm?

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;
}

-
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
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

Branch&Bounding is not what you have implemented (at least I can't see the classic algorithm in there).

Branch And Bound is normally implemented as a recursive process. I don't see recursion here. Additionally, even if the recursion is unwound to your while loop, I can't see where the efficient Branching happens.... frankly, it's a bit confusing.

Additionally, as I read your code, I believe there is a bug in that your solution will always contain items[0] (the firstNode is always pushed to the stack, and the code completes when it is popped....).

The general solution for the knapsack algorithm is to try every combination of items and find ones that fit. This is a 'combination' problem. Using recursion to find combinations is quite easy, and it is well defined using the 'branch' part of Branch and Bound.

The Bound part of the problem is that you can eliminate whole branches based on the known state of the knapsack at that branch (i.e. adding anything more from that branch will cause the conditions to fail, so you can 'prune' the whole branch). The Bound part makes the Branch part more efficient.

I believe the Branch-side of your code is broken, so the Bounds-part comes later (when you have revised/reposted the branch side).

Working on the branch side of things, the easiest thing to do is to have recursion in a for-loop......

I recommend passing a 'Branch' Object back from the recursive method, and stipulating a target weight for the branch:

public Branch branch(Item[] items, int fromposition, int target) {
if (fromposition >= items.length) {
return null;
}
Branch best = null;
for (int i = fromposition + 1; i < items.length; i++) {
Branch current = new Branch(items[i]);
// note that the recursion happens from fromposition+1
if (current.weight <= target) {
best = (best == null || current.weight > best.weight) ? current : best;
}
}
return best;
}


With the above code we calculate the 'weight' of the Branch, and we compare that to the capacity remaining in the knapsack. If we compare every combination with our knapsack we would find the solution, but not in the most efficient way. This does the Branch but nothing about Bounds.

To compute the bounds there are a few solutions.... but, starting off with sorted items leads to the most efficient solutions.... so, sort your items in ascending order.

Then, your Bounds solution becomes the simple addition of a couple of constraints:

change:

for (int i = fromposition + 1; i < items.length; i++) {


to

for (int i = fromposition + 1; i < items.length && items[i].weight <= target; i++) {


Now we stop checking our branches the moment we find that the next option is too large, and we can skip processing anything after that item because our data is sorted, and we know that the rest of the stuff is even heavier.

Another bound we can add is to stop checking when we find a perfect solution:

        if (current.weight <= target) {
best = (best == null || current.weight > best.weight) ? current : best;
}


becomes:

        if (current.weight == target) {
return current;
} else if (current.weight < target) {
best = (best == null || current.weight > best.weight) ? current : best;
}


I have just typed this in, I have not verified any of the code, but, as you can see, the solution would be:

public void knapsack2(Item[] inputitems, int maxWeight) {
// take a copy because we will sort the items...
Item[] items = Arrays.copyOf(inputitems, inputitems.length);
Arrays.sort(items, new Comparator<Item>() { ... sorts by weight...});
Branch best = branchAndBound(items, 0, maxWeight);

}

public Branch branchAndBound(Item[] items, int fromposition, int target) {
if (fromposition >= items.length) {
return null;
}
Branch best = null;
for (int i = fromposition + 1; i < items.length; i++) {
Branch current = new Branch(items[i]);
// note that the recursion happens from fromposition+1