Need help with Knapsack problem B&B

[Gldnbr]

I've got this code from the pseudo-code here:
http://books.google.com/books?id=QrvsNy9paOYC&pg=PA235&lpg=PA235&dq=knapsack+problem+branch+and+bound+C%2B%2B&source=bl&ots=e6ok2kODMN&sig=Yh5__d3iAFa5rEkaCoBJ2JAWybk&hl=en&sa=X&ei=k1EDULDrHIfKqgHqtYyxDA&ved=0CEsQ6AEwAA#v=onepage&q=knapsack%20problem%20branch%20and%20bound%20C%2B%2B&f=false

From what I'm looking at the code here, it looks like everything is fine, however it's giving strange errors, I don't even know where to begin.

#include <queue>
#include <iostream>
using namespace std;

struct node
{
	int level;
	int profit;
	int weight;
	float bound;
};

float bound(node u, int n, int W, int p[], int w[])
{
	int j, k;
	int totweight;
	float result;

	if (u.weight >= W)
	{
		return 0;
	}
	else
	{
		result = u.profit;
		j = u.level + 1;
		totweight = u.weight;
		while (j <= n && totweight + w[j] <= W)
		{
			totweight = totweight + w[j];
			result = result + p[j];
			j++;
		}
		k = j;
		if (k <= n)
		{
			result = result + (W - totweight) * p[k]/w[k];
		}
		return result;
	}
}

void knapsack(int n, int p[], int w[], int W, int& maxProfit)
{
	priority_queue<node> Q;
	node u, v;
	Q.empty();

	v.level = 0; 
	v.profit = 0;
	v.weight = 0;

	maxProfit = 0;

	v.bound = bound(v, n, W, p, w);
	Q.push(v);

	while (Q.size() > 0)
	{
		Q.pop();
		if (v.bound > maxProfit)
		{
			u.level = v.level + 1;
			u.weight = v.weight + w[u.level];
			u.profit = v.profit + p[u.level];
			if (u.weight <= W && u.profit > maxProfit)
			{
				maxProfit = u.profit;
			}
			u.bound = bound(u, n, W, p, w);
			if (u.bound > maxProfit)
			{
				Q.push(u);
			}
			u.weight = v.weight;
			u.profit = v.profit;
			u.bound = bound(u, n, W, p, w);
			if (u.bound > maxProfit)
			{
				Q.push(u);
			}
		}
	}

	system("PAUSE");
}

int main()
{
	int maxProfit;
	int n = 4;
	int W = 7;
	int p[4] = {2, 5, 3, 4};
	int w[4] = {2, 40, 18, 28};

	knapsack(n, p, w, W, maxProfit);

	cout << maxProfit << endl;

	system("PAUSE");
}

Errors:

Error 2 error C2784: 'bool std::operator <(const std::queue<_Ty,_Container> &,const std::queue<_Ty,_Container> &)' : could not deduce template argument for 'const std::queue<_Ty,_Container> &' from 'const node'

Error 3 error C2784: 'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'const node'

Error 4 error C2784: 'bool std::operator <(const std::deque<_Ty,_Alloc> &,const std::deque<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::deque<_Ty,_Alloc> &' from 'const node'

Error 5 error C2784: 'bool std::operator <(const std::unique_ptr<_Ty,_Dx> &,const std::unique_ptr<_Ty2,_Dx2> &)' : could not deduce template argument for 'const std::unique_ptr<_Ty,_Dx> &' from 'const node'

Error 6 error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'const node'

Error 7 error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'const node'

Error 8 error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'const node'

Error 9 error C2676: binary '<' : 'const node' does not define this operator or a conversion to a type acceptable to the predefined operator


Does anyone know what the problem might be?

[Gldnbr]

Okay, I don't know why, but I think it solved the problem by changing priority_queue to queue.
However, I'm still not getting the result I'm looking for, it should print 46 instead of 0.

[KRAkatau]

Well, the reason why your code doesn't work is exactly because you changed priority_queue to queue. In a nutshell, the difference between these two data structures is that the simple queue retrieves the elements in the order they were put into it, while the priority_queue retrieves the largest element among the elements stored in it. Therefore, to determine which element is largest it requires the elements to be comparable. And this is exactly what the compiler tries to tell you with its error messages: the node structures are not comparable.

You need to tell the compiler how to determine which node is smaller than the other. For example, you can do it like this:

struct node
{
	int level;
	int profit;
	int weight;
	float bound;

        bool operator<(const node& right) const
        {
                return bound < right.bound;
        }
};

Note, that I assumed that comparing bounds is what is actually necessary, but you have to double-check if this is actually what the algorithm requires you to compare.

Hope that helps.