01背包 分支限界法 代码

以下是一个使用分支限界法解决01背包问题的代码：

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    int level;
    int profit;
    int weight;
    float bound;
};

bool operator<(const Node& a, const Node& b) {
    return a.bound < b.bound;
}

float bound(Node u, int n, int W, int* p, int* w) {
    if (u.weight >= W) {
        return 0;
    }
    float result = u.profit;
    int j = u.level + 1;
    int totalWeight = u.weight;
    while ((j < n) && (totalWeight + w[j] <= W)) {
        totalWeight += w[j];
        result += p[j];
        j++;
    }
    if (j < n) {
        result += (W - totalWeight) * (p[j] / w[j]);
    }
    return result;
}

int knapsack(int n, int W, int* p, int* w) {
    priority_queue<Node> Q;
    Node u, v;
    u.level = -1;
    u.profit = 0;
    u.weight = 0;
    u.bound = bound(u, n, W, p, w);
    int maxProfit = 0;
    Q.push(u);
    while (!Q.empty()) {
        u = Q.top();
        Q.pop();
        if (u.bound > maxProfit) {
            v.level = u.level + 1;
            v.weight = u.weight + w[v.level];
            v.profit = u.profit + p[v.level];
            if (v.weight <= W && v.profit > maxProfit) {
                maxProfit = v.profit;
            }
            v.bound = bound(v, n, W, p, w);
            if (v.bound > maxProfit) {
                Q.push(v);
            }
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = bound(v, n, W, p, w);
            if (v.bound > maxProfit) {
                Q.push(v);
            }
        }
    }
    return maxProfit;
}

int main() {
    int n = 4;
    int W = 5;
    int p[] = {10, 40, 30, 50};
    int w[] = {5, 4, 6, 3};
    cout << knapsack(n, W, p, w) << endl;
    return 0;
}

希望能对你有所帮助！