Для назначения в моем классе структуры данных я предполагаю реализовать подход ветвления и ограничения для так называемой проблемы ранца. Сама проблема не является проблемой, но если вы не знаете, это проблема, связанная с поиском набора элементов, которые содержат максимальную прибыль, учитывая, что общий вес элементов не превышает переменную 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);
}
}
}
//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;
}
}
Вы пытаетесь подтолкнуть struct node
в очередь, набранную для int
, Попробуйте изменить тип PQ на priority_queue<node>