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