编辑代码

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

using namespace std;

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

    Item(string n, int v, int w) : name(n), value(v), weight(w) {}
};

void stealObjects(int packCapacity, vector<Item>& items, int curItemIndex, vector<int>& path, vector<Item>& objectsStolen) {
    if (curItemIndex == items.size()) {
        objectsStolen.clear();
        for (int index = 0; index < path.size(); ++index) {
            if (path[index] > 0) {
                objectsStolen.push_back(items[index]);
            }
        }
        return;
    }

    // 当前的最佳解
    int maxValue = 0;
    for (const auto& obj : objectsStolen) {
        maxValue += obj.value;
    }

    // 当前已选的价值和重量
    int curValue = 0;
    int curWeight = 0;
    for (int i = 0; i < curItemIndex; ++i) {
        if (path[i] > 0) {
            curValue += items[i].value;
            curWeight += items[i].weight;
        }
    }

    // 放入当前物体
    // 保证物体是能够放入，方案是可行的
    if (items[curItemIndex].weight <= packCapacity - curWeight) {
        path[curItemIndex] = 1;

        // 当前节点的边界值
        int upperValue = curValue + items[curItemIndex].value;
        if (curItemIndex < items.size() - 1) {
            const Item& nextItem = items[curItemIndex + 1];
            upperValue += (packCapacity - curWeight - items[curItemIndex].weight) * (nextItem.value / nextItem.weight);
        }

        // 边界值能超越当前最佳解
        if (upperValue > maxValue) {
            stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
        }
    }

    // 不放入当前物体
    path[curItemIndex] = 0;

    // 当前最佳解
    maxValue = 0;
    for (const auto& obj : objectsStolen) {
        maxValue += obj.value;
    }

    // 当前节点的边界值
    int upperValue = curValue;
    if (curItemIndex < items.size() - 1) {
        const Item& nextItem = items[curItemIndex + 1];
        upperValue += (packCapacity - curWeight) * (nextItem.value / nextItem.weight);
    }

    // 边界值能超越当前最佳解
    if (upperValue > maxValue) {
        stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
    }
}

vector<Item> solveBackpackProblem(int packCapacity, vector<Item>& items) {
    vector<Item> objectsStolen;
    vector<int> path(items.size(), 0);

    // 按照单价从高到低进行排序
    sort(items.begin(), items.end(), [](const Item& left, const Item& right) {
        double leftUnitPrice = static_cast<double>(left.value) / left.weight;
        double rightUnitPrice = static_cast<double>(right.value) / right.weight;
        return leftUnitPrice > rightUnitPrice;
    });

    stealObjects(packCapacity, items, 0, path, objectsStolen);
    return objectsStolen;
}

void printStolenObjects(const vector<Item>& objectsStolen) {
    for (const auto& item : objectsStolen) {
        cout << item.name << " ";
    }
    cout << endl;
}

int main() {
    vector<Item> items = {
        {"IPhone", 2000, 1},
        {"吉他", 1500, 1},
        {"笔记本电脑", 2000, 3},
        {"音箱", 3000, 4}
    };

    vector<Item> objectsStolen = solveBackpackProblem(4, items);

    cout << "偷了如下物品：" << endl;
    printStolenObjects(objectsStolen);

    int maxValue = 0;
    for (const auto& item : objectsStolen) {
        maxValue += item.value;
    }
    cout << "总价值：" << maxValue << endl;

    return 0;
}