c++:实现0-1背包问题的分支限界算法

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

struct Item {
    int weight;
    int value;
    double cost;
};

bool compare(Item i1, Item i2) {
    return (i1.cost > i2.cost);
}

double branchAndBoundKnapsack(int W, vector<Item> items) {
    sort(items.begin(), items.end(), compare);
    int currentWeight = 0;
    double finalValue = 0.0;

    for (int i = 0; i < items.size(); i++) {
        if (currentWeight + items[i].weight <= W) {
            currentWeight += items[i].weight;
            finalValue += items[i].value;
        } else {
            int remaining = W - currentWeight;
            finalValue += items[i].value * ((double) remaining / items[i].weight);
            break;
        }
    }
    return finalValue;
}

int main() {
    vector<Item> items = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}};
    int W = 50;
    double result = branchAndBoundKnapsack(W, items);
    cout << "The maximum value that can be obtained is: " << result << endl;
    return 0;
}