1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
|
#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");
}
|