c++ - 如何在 C++ 中正确使用优先级队列

Question

对于我的数据结构类中的作业，我假设要针对所谓的背包问题实现分支定界法。问题本身不是问题，但如果你不知道它是问题涉及找到包含最大利润的项目集，前提是项目的总重量不超过变量 W。有关该问题的更多信息，请参阅评论在代码中。我的问题是，当尝试使用 push 函数将节点插入优先级队列时，它会给我一些看起来像这样的错误消息

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


我过去使用过队列，但没有使用过优先级队列，而且我已经对如何在 C++ 中使用它们进行了大量研究。但是，似乎没有什么对我有用。如果有人能指出我在使用优先级队列方面做错了什么，我将不胜感激。这是我的代码，请注意所有函数都在一个名为 knapsack3.cpp 的文件中:

主要功能

 /*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); } 

背包功能

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

绑定(bind)函数

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

您正在尝试推送 struct node进入为 int 输入的队列.尝试将您的 PQ 类型更改为 priority_queue<node>