c＋＋启发式解01背包代码

在C++中，解决0/1背包问题通常使用动态规划（Dynamic Programming, DP）和启发式算法（如贪心算法或回溯法）。这里我将给出一个基于贪心策略的简单版本的启发式解法，但它不是最优的，因为0/1背包问题本身是一个NP完全问题，而贪心算法不能保证总是得到全局最优解。

**贪心策略解法（非最优）：**

#include <iostream>
#include <vector>

using namespace std;

// 函数定义：物品的价值-重量比
bool compareItems(const pair<int, int>& item1, const pair<int, int>& item2) {
    return (double)item1.second / item1.first > (double)item2.second / item2.first;
}

// 启发式解01背包
int knapsackHeuristic(vector<pair<int, int>>& items, int capacity) {
    sort(items.begin(), items.end(), compareItems); // 根据价值密度降序排序
    int weight = 0, totalValue = 0;
    for (const auto& item : items) {
        if (weight + item.second <= capacity) { // 如果剩余容量足够
            weight += item.second; // 加入物品
            totalValue += item.first; // 更新总价值
        } else { // 如果不够，取最大的价值密度
            break;
        }
    }
    return totalValue;
}

int main() {
    vector<pair<int, int>> items = {{60, 10}, {100, 20}, {120, 30}};
    int capacity = 50;
    cout << "Heuristic solution: " << knapsackHeuristic(items, capacity) << endl;
    //