Hey guys, so am working on this knapsack problem but i don't get the max profit correct. I run the code on this input:
4
16
1 40 2
2 30 5
3 50 10
4 10 5

The answer should be 90 however I get 80. Can anyone figure out what my problem is.

class Node
{
int level;
int profit;
int weight;

public String toString()
{
return level + " " + profit + " " + weight;
}
}

public int breathFirstknapsack()
{
Queue<Node> Q = new LinkedList<Node>();

v.level = 0;
v.profit = 0;
v.weight = 0;
Q.offer(v);
int maxProfit =0;
while(!Q.isEmpty())
{
Node tmp = Q.poll();
u.level = tmp.level+1;
u.weight = tmp.weight + items.get(u.level-1).getWeight();
u.profit = tmp.profit + items.get(u.level-1).getProfit();

if(u.weight <= maxWeight && u.profit > maxProfit)
maxProfit = u.profit;
if(bound(u) > maxProfit)
Q.offer(u);
u.weight = tmp.weight;
u.profit = tmp.profit;
//if(bound(u) > maxProfit)
// Q.offer(u);

}
return maxProfit;
}


public float bound(Node u)
{
int i,j;
int totalWeight = 0;;
float result;

if(u.weight >= maxWeight)
return 0;
else
{
j = u.level+1;
result = u.profit;
totalWeight = u.weight;
while(j <= numOfItems && totalWeight + items.get(j-1).getWeight() <= maxWeight)
{
totalWeight = totalWeight + items.get(j-1).getWeight();
result = result + items.get(j-1).getProfit();
j++;
}

i = j;
if(i <= numOfItems)
result = result + ((maxWeight - totalWeight) *
( (float)(items.get(i-1).getProfit())/(items.get(i-1).getWeight())) );

return result;
}
}