How to properly use priority queues in C++

Question

For an assignment in my data structure class, I am suppose to implement the branch-and-bound approach for what is known as the knapsack problem. The problem itself is not the issue, but if you do not know it is the problem involves finding the set of items that contain the maxprofit given that the total weight of the items do not exceed the variable W. More information on the problem in commented in the code. My issue is that when trying to use the push function to insert a node into the priority queue, it gives me a few error messages that look like this

no matching function for call to ‘std::priority_queue<int>::push(node&)’

I have worked with queues in the past, but not priority queues, and I have already done a considerable amount of research on how to use them in C++. However, nothing seems to work for me. If anyone can point out what it is that I am doing wrong in terms of using priority queues I will be very grateful. Here is my code, note that all functions are on one file named knapsack3.cpp:

main function

 /*Let n items be given, where each item has a weight and a profit. The weights
and profits as positive integers. Furthermore, let a positive interger W be given. 
Determine a set of items with the maximum total profit, under the condition that 
the sum of their weights cannot exceed W. */ 

//Preprocessor Directives 
#include <stdio.h>
#include <queue>
#include <iostream>    

//node data structure 
struct node { int level; int profit; int weight; float bound; }; 
using namespace std; 

//function protocol 
void knapsack3(int n, int p[], int w[], int W, int* maxprofit);
float bound(int n, int p[], int w[], int W, node u); 

//declare arrays 
int p[5]; //holds profit values for 5 items 
int w[5]; //hold weight values for 5 items 

int main() { 
//declare variables 
int n = 5; int i; int W = 13; int maxprofit = 0; 
//enter values for profit and weight in a way that each of which is sorted in
//decreasing order according to the values of p[i]/w[i] 
printf("Enter Profits\n"); 
for(i=0; i<n; i++)
    scanf("%d", &p[i]);
printf("Enter Weights\n");
for(i=0; i<n; i++)
    scanf("%d", &w[i]);

std::queue<int> PQ;
knapsack3(n, p, w, W, &maxprofit); 
//print value for maxprofit 
printf("%d\n", maxprofit); } 

knapsack function

//function that finds the maxprofit that is the sum of the profits of an optimal set.
void knapsack3(int n, int p[], int w[], int W, int* maxprofit)
{
//initialize priority queue PQ
priority_queue<int>PQ;
//initialize nodes u and v
node u, v;

//initialize PQ to be empty 
v.level = 0; v.profit = 0; v.weight = 0;
maxprofit = 0;
//initialize v to be the root
v.bound = bound(n, p, w, W, v);
PQ.push(v);

//remove node with best bound
while(!empty(PQ)){
    PQ.pop();

    //check if node is still promising
    if(v.bound > maxprofit){
        u.level = v.level + 1;
        //set node u to the child node that includes the next item
        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(n, p, w, W, u);
        if(u.bound > maxprofit)
            PQ.push(u);
        //set node u to the child node that does not include the next item
        u.weight = v.weight;
        u.profit = v.profit;
        u.bound = bound(n, p, w, W, u);
        if(u.bound > maxprofit)
            PQ.push(u);
        }
    }
}

bound function

//function that returns the bound of a node
float bound(int n, int p[], int w[], int W, node u)
{
int j, k;
int totalweight;
float result;
if(u.weight >=W)
    return 0;
else{
    result = u.profit;
    j = u.level + 1;
    totalweight + u.weight;
    while(j<=n && totalweight + w[j] <= W){
        totalweight = totalweight + w[j];
        result = result p[j];
        j++;
    }
    k=j;
    if(k<=n)
        result = result + (W-totalweight) * p[k]/w[k];
    return result;
    }
}

Answer 1

You are attempting to push a struct node into a queue typed for int. Try changing your PQ type to priority_queue<node>