编辑代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    string name;
    int value;
    int weight;
    double valuePerWeight;

    Item(const string& n, int v, int w) : name(n), value(v), weight(w), valuePerWeight(static_cast<double>(v) / w) {}

    bool operator<(const Item& other) const {
        return valuePerWeight > other.valuePerWeight;
    }
};

class KnapsackSolver {
private:
    vector<Item> items;
    int capacity;
    int bestValue;
    vector<bool> bestSolution;

    void branchAndBound(int level, int currentValue, int currentWeight, vector<bool> currentSolution) {
        if (level == items.size() || currentWeight >= capacity) {
            if (currentValue > bestValue) {
                bestValue = currentValue;
                bestSolution = currentSolution;
            }
            return;
        }

        
        if (currentValue + calculateBound(level + 1, currentWeight, currentValue, currentSolution) > bestValue) {
            branchAndBound(level + 1, currentValue, currentWeight, currentSolution);
        }

        if (currentWeight + items[level].weight <= capacity) {
            currentSolution[level] = true;
            branchAndBound(level + 1, currentValue + items[level].value, currentWeight + items[level].weight, currentSolution);
            currentSolution[level] = false;
        }
    }

    double calculateBound(int level, int currentWeight, int currentValue, const std::vector<bool>& currentSolution) {
        double bound = static_cast<double>(currentValue);

        int remainingWeight = capacity - currentWeight;

        for (int i = level; i < items.size(); ++i) {
            if (items[i].weight <= remainingWeight && !currentSolution[i]) {
                bound += items[i].value;
                remainingWeight -= items[i].weight;
            } else {
                bound += (remainingWeight / static_cast<double>(items[i].weight)) * items[i].value;
                break;
            }
        }

        return bound;
    }

public:
    KnapsackSolver(const std::vector<Item>& i, int c) : items(i), capacity(c), bestValue(0), bestSolution(i.size(), false) {}

    void solve() {
        sort(items.begin(), items.end());

        branchAndBound(0, 0, 0, vector<bool>(items.size(), false));
    }

    void printSolution() {
        cout << "偷了如下物品：" << endl;
        int totalValue = 0;
        for (size_t i = 0; i < items.size(); ++i) {
            if (bestSolution[i]) {
                cout << items[i].name << endl;
                totalValue += items[i].value;
            }
        }
        cout << "总价值" << totalValue << endl;
    }
};

int main() {
    vector<Item> items;
    items.push_back(Item("iphone", 2000, 1));
    items.push_back(Item("吉他", 1500, 1));
    items.push_back(Item("笔记本电脑", 2000, 3));
    items.push_back(Item("音响", 3000, 4));

    int capacity = 4;

    KnapsackSolver solver(items, capacity);
    solver.solve();
    solver.printSolution();

    return 0;
}