C++用贪心算法解决背包问题的实例

当用贪心算法解决背包问题时，我们需要根据一定的策略选择物品放入背包中。下面是一个用C++实现的贪心算法解决背包问题的示例：

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

using namespace std;

// 物品结构体
struct Item {
    int weight;  // 物品重量
    int value;   // 物品价值
};

// 比较函数，按照单位重量价值从大到小排序
bool compare(Item a, Item b) {
    double valuePerWeightA = (double)a.value / a.weight;
    double valuePerWeightB = (double)b.value / b.weight;
    return valuePerWeightA > valuePerWeightB;
}

// 贪心算法解决背包问题
double knapsackGreedy(vector<Item>& items, int capacity) {
    // 按照单位重量价值从大到小排序
    sort(items.begin(), items.end(), compare);

    double totalValue = 0.0;  // 总价值
    int currentWeight = 0;    // 当前背包重量

    for (int i = 0; i < items.size(); i++) {
        if (currentWeight + items[i].weight <= capacity) {
            // 如果当前物品可以完全放入背包中
            currentWeight += items[i].weight;
            totalValue += items[i].value;
        } else {
            // 如果当前物品只能部分放入背包中
            int remainingCapacity = capacity - currentWeight;
            totalValue += (double)remainingCapacity / items[i].weight * items[i].value;
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
    int capacity = 50;

    double maxValue = knapsackGreedy(items, capacity);
    cout << "背包能够装下的最大价值为：" << maxValue << endl;

    return 0;
}