编辑代码

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int level, profit, weight;
    double bound;
};

struct CompareNode {
    bool operator()(const Node& n1, const Node& n2) {
        return n1.bound < n2.bound;
    }
};

double bound(const Node& u, int n, int W, int* values, int* weights) {
    if (u.weight >= W) {
        return 0;
    }

    double profitBound = u.profit;
    int j = u.level + 1;
    int totalWeight = u.weight;

    while (j < n && totalWeight + weights[j] <= W) {
        totalWeight += weights[j];
        profitBound += values[j];
        j++;
    }

    if (j < n) {
        profitBound += (W - totalWeight) * (static_cast<double>(values[j]) / weights[j]);
    }

    return profitBound;
}

int knapsack(int W, int* values, int* weights, int n) {
    priority_queue<Node, vector<Node>, CompareNode> priorityQueue;

    Node u{-1, 0, 0, 0.0};

    int maxProfit = 0;

    priorityQueue.push(u);

    while (!priorityQueue.empty()) {
        u = priorityQueue.top();
        priorityQueue.pop();

        if (u.level == n - 1) {
            continue;
        }

        Node v{u.level + 1, u.profit + values[u.level + 1], u.weight + weights[u.level + 1]};

        if (v.weight <= W && v.profit > maxProfit) {
            maxProfit = v.profit;
        }

        v.bound = bound(v, n, W, values, weights);

        if (v.bound > maxProfit) {
            priorityQueue.push(v);
        }

        Node w{u.level + 1, u.profit, u.weight};

        w.bound = bound(w, n, W, values, weights);

        if (w.bound > maxProfit) {
            priorityQueue.push(w);
        }
    }

    return maxProfit;
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(values) / sizeof(values[0]);

    int maxValue = knapsack(W, values, weights, n);

    cout << "Maximum value in Knapsack = " << maxValue << endl;

    return 0;
}