一般背包问题c++贪心法

背包问题一般分为 01 背包、完全背包和多重背包，这里以 01 背包问题为例，介绍 C++ 中的贪心算法实现。

01 背包问题是指有 N 种物品和一个容量为 V 的背包，每种物品都只有一个，第 i 种物品的体积为 v[i]，价值为 w[i]。求将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

贪心算法的思路是将物品按照单位体积的价值从大到小排序，然后依次选取单位体积价值最大的物品放入背包中，直到背包装满或者所有物品都被选完为止。

以下是 C++ 代码实现：

#include <iostream>
#include <algorithm>

using namespace std;

struct item {
    int v; // 体积
    int w; // 价值
    double vw; // 单位体积价值
};

bool cmp(item a, item b) {
    return a.vw > b.vw;
}

int main() {
    int n, V;
    cin >> n >> V;

    item items[n];
    for (int i = 0; i < n; i++) {
        cin >> items[i].v >> items[i].w;
        items[i].vw = (double)items[i].w / items[i].v;
    }

    sort(items, items + n, cmp);

    int ans = 0;
    for (int i = 0; i < n && V > 0; i++) {
        int cnt = min(items[i].v, V);
        ans += cnt * items[i].vw;
        V -= cnt;
    }

    cout << ans << endl;

    return 0;
}

在这个代码中，我们定义了一个结构体 `item` 表示物品，包含体积、价值和单位体积价值三个属性。然后我们定义了一个比较函数 `cmp`，用于将物品按照单位体积的价值从大到小排序。接着，我们输入物品信息，并计算单位体积价值，最后按照贪心算法的思路依次选取物品放入背包中，直到背包装满或者所有物品都被选完为止，最终输出总价值。

需要注意的是，在代码中我们选取物品时采用了分数选取，即一个物品可以被选取部分，因此我们使用了一个变量 `cnt` 表示当前物品被选取的数量。