编辑代码

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

// 物品结构体
struct Item {
    int weight;
    int value;
};

// 按照单位价值排序的比较函数
bool cmp(Item a, Item b) {
    return (double(a.value) / a.weight) > (double(b.value) / b.weight);
}

double fractionalKnapsack(int capacity, vector<Item>& items, int idx,
                          double valueSoFar) {
    // 如果背包已满或者所有物品都已考虑完，返回当前总价值
    if (capacity == 0 || idx == items.size()) {
        return valueSoFar;
    }
    // 当前物品能完全放入背包时，直接加入总价值，将背包容量减去当前物品重量
    if (items[idx].weight <= capacity) {
        valueSoFar += items[idx].value;
        capacity -= items[idx].weight;
    } else {
        // 当前物品不能完全放入背包时，计算剩余容量能装的比例
        double fraction = double(capacity) / items[idx].weight;
        valueSoFar += items[idx].value * fraction;
        capacity = 0;
    }
    // 递归考虑下一个物品，更新总价值
    return fractionalKnapsack(capacity, items, idx + 1, valueSoFar);
}

double branchAndBoundKnapsack(int capacity, vector<Item>& items) {
    // 按照单位价值从大到小排序物品
    sort(items.begin(), items.end(), cmp);
    // 初始价值为0，下一个物品索引为0
    double valueSoFar = 0;
    int idx = 0;
    // 使用分支界限法解决背包问题
    return fractionalKnapsack(capacity, items, idx, valueSoFar);
}

int main() {
    // 创建物品向量
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
    // 背包容量
    int capacity = 50;
    // 计算背包能够装下的最大价值
    double maxValue = branchAndBoundKnapsack(capacity, items);
    cout << "背包能够装下的最大价值为：" << maxValue << endl;
    return 0;
}