最优装载问题贪心c++

最优装载问题，也称为背包问题（Knapsack Problem），在计算机科学中是一个经典的组合优化问题，通常涉及到如何在给定容量限制下，选择物品以获得最大的价值。在C++中，解决这类问题的一种常见方法是使用贪心算法，特别是针对0-1背包问题（每个物品只能取一次）。

贪心算法策略是每次选择当前状态下能够提供最大收益（价值/重量比）的物品放入背包，直到达到背包的容量。以下是使用贪心策略解决0-1背包问题的一个简单C++实现：

#include <iostream>
#include <vector>

// 定义物品类
struct Item {
    int weight; // 重量
    int value; // 价值
};

// 贪心函数，返回包含在背包中的最大总价值
int greedyKnapsack(std::vector<Item>& items, int capacity) {
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) { return (a.value / a.weight) > (b.value / b.weight); }); // 按价值/重量比率排序

    int totalValue = 0;
    for (const auto& item : items) {
        if (capacity >= item.weight) { // 如果有足够空间，添加当前物品
            totalValue += item.value;
            capacity -= item.weight; // 更新背包容量
        } else { // 如果超出容量，选择部分物品
            totalValue += item.value * (capacity / item.weight);
            break; // 停止添加，因为剩余容量不足以再放一个完整的物品
        }
    }
    return totalValue;
}

int main() {
    std::vector<Item> items = {{60, 100}, {100, 200}, {120, 300}}; // 一些物品及其重量和价值
    int capacity = 500; // 背包容量
    int maxTotalValue = greedyKnapsack(items, capacity);
    std::cout << "Max total value with greedy approach: " << maxTotalValue << std::endl;
    return 0;
}